題目鏈接在這里
http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1026
題意很簡單：從起始點開始走，最多可以走K步，只能向左，向右，向前走，地圖上有一些豆豆，問你最多可以吃到多少豆豆。其實這個題可以這么看，每兩個豆豆之間的最短距離是固定的，我們的目的是吃豆豆，不是來玩的，所以就是一個最短哈密頓路徑問題，當(dāng)然題目有一些限制。上篇博客里寫的那個用一條鏈把N個點串起來，求最短長度問題和這個問題是類似的，但是那個題作者給出了一個DP解法，我表示很疑惑。如果看懂了作者的那個辦法，這個題就瞬秒了(
哪位大神知道求指點)。上一篇在這里。
http://m.shnenglu.com/a542343910/archive/2012/04/06/170309.html。
好吧，既然不是大神，就自己寫個搜索吧。如果按照普通的那種搜索的辦法，每次左走一格，右走一格，前面走一格，超時超死你。額，這就要構(gòu)造出這個題的類似貪心的搜索了。上面我們已經(jīng)說過了，實際上我們是為了吃豆豆來的，每次從一個點，都要徑直走到另一個豆豆。這樣就很明了了：我們每次只要向左走，找個豆豆吃掉，向右走，找個豆豆吃掉，再向前走。就可以了。但是問題來了，會不會在當(dāng)前行沒吃豆豆，但是走了一些長度呢？我們分析下有沒有可能這做
。假如我們向右走了K步，沒吃到豆豆，我們可以把這K步轉(zhuǎn)嫁到下一行，那樣這K步就有可能發(fā)揮作用吃到一個豆豆了，再來看最后一行，如果我們在最后一行走了無用的K步，也是毫無意義的。至此貪心的性質(zhì)證明出來了。搜索是個非常靈活的東西，也是可以有非常多拓展的東西。最重要的是，很有趣。
在寫程序的時候，剛剛開始沒考慮清楚，只用了flag[]記錄當(dāng)前行剩下的豆豆，沒有記錄某個豆豆是否被吃掉（豆豆可能被重復(fù)吃掉），錯了一次。后面又粗心寫錯了一點，汗。。。
好了，還有個更有趣的事情：這個題我開始是想用DP做的，并且寫出了個錯誤的DP程序。狀態(tài)如下：r[i][j][k]，到達(dá)點i,j走了K步用的最小步長，可以證明，只要按照k遞增序枚舉就可以。咋一看5X9X100狀態(tài)很少，不錯。但是后來發(fā)現(xiàn)，同一個狀態(tài)不是具有最優(yōu)子結(jié)構(gòu)的，因為可能吃了不同的豆豆到達(dá)了相同的狀態(tài)。So，錯了。能不能換一種方式DP呢？我想到了一個具有最優(yōu)子結(jié)構(gòu)的解法，r[i][j][k]表示吃掉了i行的所有豆豆，停留在i,j，走了K步最多吃的豆豆數(shù)目。額，這樣固然可以，但是。。。。題目說可以忽略一些豆豆。。。。哈哈，又胡思亂想了。好了，這幾天一直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;
}
.