我的狀態壓縮的第一題，忘記取模錯了2次。

符合的狀態000 001 010 100 101 ?記得和該行原來狀態看是否符合。

#include<cstdio> #include<iostream> #include<cstring> using namespace std; int dp[13][1<<14],state[1<<14],cur[13]; int m,n,top; const int one_one=100000000; void Init() {int total=1<<n,i;for(i=0;i<total;i++){if(i&(i<<1))continue;elsestate[top++]=i;} } bool fit(int a,int b) {if(a&b)return false;return true; } void Dp() {int i,j,k;for(i=0;i<top;i++){if(fit(cur[1],state[i]))dp[1][i]=1;}for(i=2;i<=m;i++){for(j=0;j<top;j++){if(!fit(cur[i],state[j])) continue;else{for(k=0;k<top;k++){if(!fit(cur[i-1],state[k])) continue;if(fit(state[j],state[k])) dp[i][j]=(dp[i][j]+dp[i-1][k])%one_one;}}}}int ans=0;for(i=0;i<top;i++){ans=(ans+dp[m][i])%one_one;}printf("%d\n",ans); } int main() {int i,j,temp;scanf("%d %d",&m,&n);for(i=1;i<=m;i++){for(j=1;j<=n;j++){scanf("%d",&temp);if(temp==0)cur[i]+=1<<(n-j);}}top=0;memset(dp,0,sizeof(dp));Init();Dp(); }

總結

以上是生活随笔為你收集整理的POJ 3254 状态压缩DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。