额,,,铺砖块问题的第一题,,,,嘤嘤我没有自己DEBUG,我的错,,下次打死都不再这样了。
然后主要是两个坑:
数据到后来会很大,要用int64,然后是数组范围,要开到11*(1<<11) 不过不知道为什么。。。。
啊然后是注意想清楚为什么是相加。
#include <stdio.h> #include <string.h> #define maxn 3000 int path[15000][2],dp[13][maxn],h,w,ans,tan; void dfs(int d,int now,int pre) { if(d>w) return; if(d==w) { path[tan][1]=now; path[tan++][0]=pre; } dfs(d+1,now<<1|1,pre<<1); //当前位置竖着铺一块砖,所以上一行当前位置一定不能是竖着铺的,只能横着铺 dfs(d+2,now<<2|3,pre<<2|3); //当前位置横着铺,那么在这两格内,上一行一定不能有竖着铺的,所以都要是横着的 <span style="font-family: Arial, Helvetica, sans-serif;">dfs(d+1,now<<1,pre<<1|1); //当前位置不铺,因为上一行竖着铺下来占到位置了</span>
} int max(int x,int y) { if(x>y) return x; else return y; } int main() { while(scanf("%d%d",&h,&w)!=EOF&&h+w) { ans=-1; if(w>h) {int tmp=w;w=h;h=tmp;} memset(dp,0,sizeof(dp)); tan=0; dfs(0,0,0); int i,j,k; // for(i=0;i<tan;i++) dp[0][path[i][0]]=1; dp[0][(1<<w)-1]=1; //第0行要铺满,一定存在这种情况,因为第一行不能被上一行占领。 for(i=0;i<h;i++) { for(j=0;j<tan;j++) dp[i+1][path[j][1]]+=dp[i][path[j][0]]; //从第一行开始枚举,将所处理出来的合法状态叠加。 } // for(i=0;i<tan;i++) ans=max(ans,dp[h][path[i][(1<<w]-1]); ans=dp[h][(1<<w)-1]; //取最后一行被铺满的状态 printf("%d\n",ans); } return 0; }