这道题是zp推荐的，说是一道动态规划题，做完后觉得这就是我最不认为是dp的一种dp题,他的思想和那种给你一个地图，起始位置在左上角，终点位置在右下角，每个位置上都有一定的宝藏，规定了每次只能往右走一步，或是往下走一步。。然后问你最后能取得的宝藏最大值，开始我就不认为这种题是dp，他的状态只会和前一状态有关。而1029这个题就是这样子的。
下面是我做这个题之前别人的提示，有几个关键字：
2^n个状态,n为列数，我们做到按行更新，更新一行的时候我们按列来，如果更新到最后一列，则换下一行。
更新当前行时和上一行有关。
这两句话给了开始的模糊印象。。但是确实有点抽象
下面是cpg2001
用横线来划分阶段，对于图一，虽然划分后很整齐，但把某些砖分成了两半，于是将他们也添加进来，于是变成了图二，其显得参差不齐，但最多也是向下突出一格，在图三中，我们将图二的空隙填满，则又转移到了下一种状态。
定义添砖小块状态为1,否则为0,则每行状态可以映射到一个数(0,2^h})于是可建立这样的状态a[ i ：j]：表示第i行填满，第i+1行对应状态为j时的不同方案数，a[I,j]=∑a[i-1,k]，其中，状态k可导出状态j,初始化条件a[0,0]=1，最后a[w,0]即为所求。
的启发，再加上zp的讲解逐渐清晰起来：
行数我们默认是从0开始
第三行的赋值情况 ：000011
第四行的赋值情况 ：100100
第五行的赋值情况 ：011000
图一：第三行填满了，第三行的第一个格子是一个竖形格子，这个竖形格子的上格子在第三行，下格子在第四行，于是在第四行需要补格子故置为1，第三行的第二个第三个格子是个横条，我们都置为0，紧接着又是一个竖形格子的上半个格子，同样是0，下面两个都是竖形格子的下半个置为1
同理将分别对第四行第五行赋值
比如图二的第四行，第二第三个两个连续的零，还有一种方案是摆一个横条。
其他的详见注释。
我的代码：
#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-->头顶上的那个格子状态，uprt-->头顶上的右边的那个格子的状态
if(j==M)
{
if(!up)solve(j+1,last,now*2+1);//就剩一个空了，并且上面的那个是0，那么显然是竖条
//这一行需要补一个小方格
//如果上面是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//这个地方时很容易出错的，我这里认为是第j列置为0
//可以理解为是一个竖形条状的上半个格子，也可以认为是一个横行条状的左半个格子
//这里千万不能把这两种情况分开计算，这样会重复的
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 阅读(782)
评论(2) 编辑 收藏 引用 所属分类:
acm 、
动态规划