您正在查看 "搜索专栏" 分类下的文章 2010-10-28 16:36
/*算法：DFS+剪枝：
剪枝1：如果当前已经达到了9步，而当前点与目标点不在同一线上可以return
剪枝2：如果当前步数+1大于已经得出的最小结果步数，则return;
32ms
*/
#include <cstdio>
#include <cstring> |
2010-10-26 16:37 双向BFS初级练习：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include |
2010-10-18 22:48 令dp[ i ][ j ] 表示在到达第i个城市后还剩余j单位油所消费的最低的钱，那么可以从源点到汇点进行费用松驰操作，其实就是相当于DP，只不过用搜索来实现去了，为了保持最优，得用优先队列进行存储，我用STL的优先队列三百多ms, 手写的优先队列居然要四百多，可能是在数组那里开得比较大，手写的这里不好申请优先队列的数组大小，
|
2010-10-15 19:34 题意：略
算法描述：昨天写了一个纯BFS的，结果TLE，把STL的队列改为手写的队列之后WA了N次才AC，原来是没有考虑蛇头已经在出口时的情况，最终两千多ms过掉了，最后参考了大牛写的A*算法，和位存储状态，于是我也试着写了一下，位运算火候不到家，写得很痛苦啊，好不容易写完了，过了样例，WA，随机测了一组数组，没过，发现是 int CC = (cur&31) + direction[ i ][ 1 ]; 这里位运算那里没有加括号，对于位运算，如果不是非常清楚其优先级还是最好老老实实的加上括号，加了之后，提交，AC |
2010-10-13 10:53 纯搜索题，第一次完成代码量5k以上的搜索题（加上一些注释）我用的单向BFS，最终一千多ms过了，把队列改成手写的，也是一千五百多ms,以为是数组开大了，于是加上滚动数组，居然一千七百多ms.这种题在比赛的时候就算知道怎么做，但想A感觉也不是一时半会的事，还是多练代码能力吧
|
2010-10-11 21:20 题意：略
分析：一看就是搜索，不过写起来还是有点麻烦，处理的细节稍微多了一点，代码量感觉不好控制，接近3.5k, 需要注意的细节：如果走两步或三步，要判断中间是否能通过， 还有是否已经走过（注意：这里只与该步的终点有关，与这一步的路上状态无关），还有就是不能在边界上面走，
PS：写完代码，果断出不了样例，最后发现了有四五个地方小错误，改了，过了样例，提交（坚信99%会WA，没想到返回accepted,爽）
|
2010-08-15 16:07 WA了几次，测试了十多个数据也没有找出错误，还是只有慢慢检查代码吧，看了半天终于找到咯
算法：先二分答案，然后枚举最低高度，再dfs判断是否可以连通
#include <iostream>
#include <vector>
|
2010-08-01 16:47 算法：此题容易想出状态转移方程，不过我感觉很多种情况没有必要计算，于是我用了记忆化搜索，若到达某个点的最大值已经计算过，则设置一个标记，还要注意的是，初始化的时候不能初始化为0，因为可能存在负数的情况，
#include <iostream>
#include |
2010-07-16 16:01 题目大意：给定n种不同的邮票（可能给定的值是一样的，但类型得看成不同），当某人需求总面值为m的邮票时，向他提供类型最多方案的邮票（限制条件：邮票总数不以超过四）如果有多种类型相同的最佳方案，则选择邮票数目最少的一种。如果此时邮票数目相等，则选择其中数目最大的中的一种方案，如果又有两种以上的方案，则输出"tie";
算法：DFS搜索+剪枝
剪枝：假如当前已经搜索到的邮票数为m，剩下还可以继续搜的邮票总数为n,如果m+n小于当前最优结果的类型总数则不必再继续搜，
|
2010-07-15 20:07 题意：略
此题最重要的有两个剪枝条件：1：如果当前另起一根，则从剩下的棍子里选择长度最长的一根，如果此根搜索失败则不必再搜，2：如果当前某根搜索失败，而此根棍子的长度加上此次还原棍子的剩余长度等于正在尝试搜索的棍子原长（慢慢体会）则不必再搜索，原因是因为如果此次搜索失败，而此假设的棍子原长成立，那么在剩余的棍子里面能找出一些棍子来填补此次搜索当前棍子的剩余长度，而当前搜索失败的这根棍子必定会在以后还原棍子中被用到，那么显然这根棍子和那些棍子（填补此次搜索的该棍子的剩余长度的棍子）能 |
2010-06-10 23:36 注意：直接BFS肯定是不行的。
#include <iostream>
#include <queue>
using namespace std;
const int maxn=310;
int m, n;
char map[maxn][maxn];
int st, ed;
int direction[5][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {0, 0}};
bool visit[maxn][maxn];
struct Point
{
int x, y, t;
bool operator<(const Point &a)const
{
return a.t < t;
}
|
2010-06-06 11:51 此题偶在WA二十次以上的情况下终于艰难的AC了。一次次无奈的WA让偶感觉到切心之痛啊。测试数据生成如此之多却也找不出bug。
算法描述：优先队列+搜索，（也可以不用优先队列），
先说一下我的代码为什么一直WA；
最主要的情况是下面这里：
for (int j=0; j<4; j |
2010-05-23 23:02 不想说什么：只想保持沉默。
#include <iostream>
#include <vector>
#include <set>
#include <string>
using namespace std;
int T;
int n, m;
int num[20];
set< vector<int> >s;
string s1;
vector<int> v;
void dfs(int i, int val)
{
if(i>m+1 || val>n) return;
if(val==n)
|
2010-05-04 14:48 2010-04-20 23:35 #include <iostream>
using namespace std;
int difx, dify;
struct SEG
{
int l, c;
}seg[5];
bool visitx[5];
bool visity[5];
int bestsol;
int k;
void dfsy(int tot, int num, int i)
{
if(num>=bestsol) return;
if(tot==dify)
{
bestsol=num;
return; //出现的第一个答案就是最佳的答案
}
for (; i<=k; i++)
{
if(visity[i] || !seg[i].c) continue;
visity[i]=1;
for (int j=1; j<=seg[i].c; j++)
{
|
| | |
