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