题目链接在这里
http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1026
题意很简单：从起始点开始走，最多可以走K步，只能向左，向右，向前走，地图上有一些豆豆，问你最多可以吃到多少豆豆。其实这个题可以这么看，每两个豆豆之间的最短距离是固定的，我们的目的是吃豆豆，不是来玩的，所以就是一个最短哈密顿路径问题，当然题目有一些限制。上篇博客里写的那个用一条链把N个点串起来，求最短长度问题和这个问题是类似的，但是那个题作者给出了一个DP解法，我表示很疑惑。如果看懂了作者的那个办法，这个题就瞬秒了(
哪位大神知道求指点)。上一篇在这里。
http://www.cppblog.com/a542343910/archive/2012/04/06/170309.html。
好吧，既然不是大神，就自己写个搜索吧。如果按照普通的那种搜索的办法，每次左走一格，右走一格，前面走一格，超时超死你。额，这就要构造出这个题的类似贪心的搜索了。上面我们已经说过了，实际上我们是为了吃豆豆来的，每次从一个点，都要径直走到另一个豆豆。这样就很明了了：我们每次只要向左走，找个豆豆吃掉，向右走，找个豆豆吃掉，再向前走。就可以了。但是问题来了，会不会在当前行没吃豆豆，但是走了一些长度呢？我们分析下有没有可能这做
。假如我们向右走了K步，没吃到豆豆，我们可以把这K步转嫁到下一行，那样这K步就有可能发挥作用吃到一个豆豆了，再来看最后一行，如果我们在最后一行走了无用的K步，也是毫无意义的。至此贪心的性质证明出来了。搜索是个非常灵活的东西，也是可以有非常多拓展的东西。最重要的是，很有趣。
在写程序的时候，刚刚开始没考虑清楚，只用了flag[]记录当前行剩下的豆豆，没有记录某个豆豆是否被吃掉（豆豆可能被重复吃掉），错了一次。后面又粗心写错了一点，汗。。。
好了，还有个更有趣的事情：这个题我开始是想用DP做的，并且写出了个错误的DP程序。状态如下：r[i][j][k]，到达点i,j走了K步用的最小步长，可以证明，只要按照k递增序枚举就可以。咋一看5X9X100状态很少，不错。但是后来发现，同一个状态不是具有最优子结构的，因为可能吃了不同的豆豆到达了相同的状态。So，错了。能不能换一种方式DP呢？我想到了一个具有最优子结构的解法，r[i][j][k]表示吃掉了i行的所有豆豆，停留在i,j，走了K步最多吃的豆豆数目。额，这样固然可以，但是。。。。题目说可以忽略一些豆豆。。。。哈哈，又胡思乱想了。好了，这几天一直TILE，今天写出了个比较满意的，贴之。怨念下matlab。#include <cstdio>#include <cstring>
char data[10][10];
int N;
int flag[10];
int vis[10][10];
int ans,maxcount;
void dfs(int x,int y,int step,int count)
{
if(step > N)
return;
if(ans < count)
ans = count;
if(ans == maxcount)
return;
int i;
if(flag[x] > 0)
{
i = y-1;
while(i>=0 && data[x][i] != 'K' || vis[x][i])
i--;
if(i>=0 && (step + y-i)<= N)
{
flag[x]--;
vis[x][i] = 1;
dfs(x,i,step+y-i,count+1);
vis[x][i] = 0;
flag[x]++;
}
i =y+1;
while(i<9 && data[x][i] != 'K' || vis[x][i])
i++;
if(i<9 && step+i-y <= N)
{
flag[x]--;
vis[x][i] = 1;
dfs(x,i,step+i-y,count+1);
vis[x][i] = 0;
flag[x]++;
}
}
if(x-1>=0)
{
if(data[x-1][y] == 'K')
{
flag[x-1]--;
vis[x-1][y] = 1;
dfs(x-1,y,step+1,count+1);
vis[x-1][y] = 0;
flag[x-1]++;
}
else
dfs(x-1,y,step+1,count);
}
}
int main()
{
//freopen("in_1026.txt","r",stdin);
//freopen("out.txt","w",stdout);
int testcount,sx,sy,i,j;
scanf("%d",&testcount);
while(testcount--)
{
memset(flag,0,sizeof(flag));
memset(vis,0,sizeof(vis));
scanf("%d",&N);
for(i=0;i<5;i++)
scanf("%s",data[i]);
sx = sy = -1;
for(i=0;i<5;i++)
{
for(j=0;j<9;j++)
{
if(data[i][j] == 'K')
flag[i]++;
if(data[i][j] == 'L')
{
sx = i;
sy = j;
}
}
}
maxcount = 0;
for(i=sx;i>=0;i--)
maxcount += flag[i];
ans = 0;
dfs(sx,sy,0,0);
printf("%d\n",ans);
}
return 0;
}
.