POJ 3254 简单状压DP-白红宇的个人博客

POJ 3254 简单状压DP

发布日期：2021-08-17 10:07:45 浏览次数：43 分类：技术文章

本文共 1182 字，大约阅读时间需要 3 分钟。

没什么可说的，入门级状压DP。直接撸掉

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                #define LL long long#define FOR(i, x, y) for(int i=x;i<=y;i++)using namespace std;const int maxn = 5000;const int MOD = 100000000;int N, M, K;int C[20], state[maxn];int dp[20][maxn];bool judge(int x){ if(x & (x << 1)) return false; return true;}void init(){ memset(dp, 0, sizeof(dp)); memset(state, 0, sizeof(state)); memset(C, 0, sizeof(C)); int r = (1 << M) - 1; K = 0; FOR(i, 0, r) if(judge(i)) state[++K] = i;}int main(){ while(scanf("%d %d", &N, &M)!=EOF) { init(); int X; FOR(i, 1, N) FOR(j, 1, M) { scanf("%d", &X); if(X == 0) C[i] = C[i] | (1 << (M - j)); } FOR(i, 1, K) { if(!(state[i] & C[1])) dp[1][i] = 1; } FOR(i, 2, N) FOR(j, 1, K) { if(C[i-1] & state[j]) continue; FOR(l, 1, K) { if((C[i] & state[l]) || (state[l] & state[j])) continue; dp[i][l] = (dp[i-1][j] + dp[i][l]) % MOD; } } int ans = 0; FOR(i, 1, K) ans = (ans + dp[N][i]) % MOD; printf("%d\n", ans); } return 0;}

转载于:https://www.cnblogs.com/claireyuancy/p/7353767.html

转载地址：https://blog.csdn.net/weixin_30846599/article/details/99207092 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：细说linux IPC（三）：mmap系统调用共享内存

下一篇：HBase多条件筛选查询方案

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章