這道題是zp推薦的，說(shuō)是一道動(dòng)態(tài)規(guī)劃題，做完后覺(jué)得這就是我最不認(rèn)為是dp的一種dp題,他的思想和那種給你一個(gè)地圖，起始位置在左上角，終點(diǎn)位置在右下角，每個(gè)位置上都有一定的寶藏，規(guī)定了每次只能往右走一步，或是往下走一步。。然后問(wèn)你最后能取得的寶藏最大值，開始我就不認(rèn)為這種題是dp，他的狀態(tài)只會(huì)和前一狀態(tài)有關(guān)。而1029這個(gè)題就是這樣子的。
下面是我做這個(gè)題之前別人的提示，有幾個(gè)關(guān)鍵字：
2^n個(gè)狀態(tài),n為列數(shù)，我們做到按行更新，更新一行的時(shí)候我們按列來(lái)，如果更新到最后一列，則換下一行。
更新當(dāng)前行時(shí)和上一行有關(guān)。
這兩句話給了開始的模糊印象。。但是確實(shí)有點(diǎn)抽象
下面是cpg2001
用橫線來(lái)劃分階段，對(duì)于圖一，雖然劃分后很整齊，但把某些磚分成了兩半，于是將他們也添加進(jìn)來(lái)，于是變成了圖二，其顯得參差不齊，但最多也是向下突出一格，在圖三中，我們將圖二的空隙填滿，則又轉(zhuǎn)移到了下一種狀態(tài)。
定義添磚小塊狀態(tài)為1,否則為0,則每行狀態(tài)可以映射到一個(gè)數(shù)(0,2^h})于是可建立這樣的狀態(tài)a[ i ：j]：表示第i行填滿，第i+1行對(duì)應(yīng)狀態(tài)為j時(shí)的不同方案數(shù)，a[I,j]=∑a[i-1,k]，其中，狀態(tài)k可導(dǎo)出狀態(tài)j,初始化條件a[0,0]=1，最后a[w,0]即為所求。
的啟發(fā)，再加上zp的講解逐漸清晰起來(lái)：
行數(shù)我們默認(rèn)是從0開始
第三行的賦值情況 ：000011
第四行的賦值情況 ：100100
第五行的賦值情況 ：011000
圖一：第三行填滿了，第三行的第一個(gè)格子是一個(gè)豎形格子，這個(gè)豎形格子的上格子在第三行，下格子在第四行，于是在第四行需要補(bǔ)格子故置為1，第三行的第二個(gè)第三個(gè)格子是個(gè)橫條，我們都置為0，緊接著又是一個(gè)豎形格子的上半個(gè)格子，同樣是0，下面兩個(gè)都是豎形格子的下半個(gè)置為1
同理將分別對(duì)第四行第五行賦值
比如圖二的第四行，第二第三個(gè)兩個(gè)連續(xù)的零，還有一種方案是擺一個(gè)橫條。
其他的詳見注釋。
我的代碼：
#include<iostream>
#define max(a,b) (a>b?a:b)
int N,M,maxl=0;
__int64 ans[3000],tmp[3000];
void solve(int j,int last,int now)
{
if(j>M)
{
tmp[now]+=ans[last];
maxl=max(maxl,now);
return;
}
int up=(1<<(M-j))&last,uprt;
//up-->頭頂上的那個(gè)格子狀態(tài)，uprt-->頭頂上的右邊的那個(gè)格子的狀態(tài)
if(j==M)
{
if(!up)solve(j+1,last,now*2+1);//就剩一個(gè)空了，并且上面的那個(gè)是0，那么顯然是豎條
//這一行需要補(bǔ)一個(gè)小方格
//如果上面是1，顯然下面仍然是要接著一個(gè)豎條，但是這個(gè)小方格是上面這半個(gè)，無(wú)需置1
else solve(j+1,last,now*2);
}
else
{
uprt=(1<<(M-j-1))&last;
if(!up)
{
solve(j+1,last,now*2+1);
if(!uprt)//如果頭頂上的不為0，頭頂上右邊的也不為0，下面的就可以放一個(gè)橫條
solve(j+2,last,now*4);
}
else//這個(gè)地方時(shí)很容易出錯(cuò)的，我這里認(rèn)為是第j列置為0
//可以理解為是一個(gè)豎形條狀的上半個(gè)格子，也可以認(rèn)為是一個(gè)橫行條狀的左半個(gè)格子
//這里千萬(wàn)不能把這兩種情況分開計(jì)算，這樣會(huì)重復(fù)的
solve(j+1,last,now*2);
}
}
int main()
{
int i,j;
while(scanf("%d%d",&N,&M)&&N)
{
if((N*M)%2)
{
printf("0\n");
continue;
}
memset(ans,0,sizeof(ans));
ans[0]=1;
for(i=1;i<=N;i++)
{
memset(tmp,0,sizeof(tmp));
for(j=0;j<=maxl;j++)
if(ans[j])solve(1,j,0);
memcpy(ans,tmp,sizeof(tmp));
}
printf("%I64d\n",ans[0]);
}
return 0;
}posted on 2008-07-08 14:01
zoyi 閱讀(809)
評(píng)論(2) 編輯 收藏 引用 所屬分類:
acm 、
動(dòng)態(tài)規(guī)劃