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