您的位置: 首页  >  IT文章  >  状态压缩DP

状态压缩DP

分类: IT文章 • 2022-05-29 12:28:17

萌新第一题：POJ3524 注释都写了，转移方程那里没写

 1 #include <iostream>
 2 #include <string.h>
 3 #include <cstdio>
 4 #include <queue>
 5 #include <string>
 6 #include <algorithm>
 7 #define SIGMA_SIZE 26
 8 #pragma warning ( disable : 4996 )
 9 
10 using namespace std;
11 typedef long long LL;
12 
13 inline int Max(int a,int b) { return a>b?a:b; }
14 inline int Min(int a,int b) { return a>b?b:a; }
15 inline int gcd( int a, int b ) { return b==0?a:gcd(b,a%b); }
16 inline int lcm( int a, int b ) { return a/gcd(a,b)*b; }  //a*b = gcd*lcm
17 const int inf = 0x3f3f3f3f;
18 const int maxn = 13;
19 const int maxk = 1<<maxn;
20 const int mod = 100000000;
21 
22 int stage[maxk],map[maxn];    //一共N列，所以可表示的二进制数的范围是1<<N，其中没有相邻1的数字记录在stage中
23 int dp[maxn][maxk];
24 int N, M, top;
25 
26 inline bool ok(int x)
27 { return !(x&(x<<1)); }        //一个数字x的二进制表示中，如果有相邻的1则返回false
28 
29 inline bool fit(int i, int x)            //因为map[i]的二进制中，1代表不能放牧
30 { return !(map[i]&stage[x]); }            //而stage[x]的二进制,1代表可以放牧，
31                                         //所以当1&1=1时，即代表在不可放牧的格子上放牧了
32 
33 void init()
34 {
35     memset( stage, 0, sizeof(stage) );
36     memset( map, 0, sizeof(map) );
37     memset( dp, 0, sizeof(dp) );
38 
39     top = 0;
40     int tot = 1 << N;                    //数字最多只能到1 << N(二进制)
41     for ( int i = 0; i < tot; i++ )        //且不能等于1<<N
42         if (ok(i))                        //若这个数字的二进制表示没有相邻的1(满足放牧规则)
43             stage[top++] = i;            //则将其存在stage中
44 }
45 
46 int main()
47 {
48     
49     while ( ~scanf("%d %d", &M, &N) )
50     {
51         init();
52 
53         int x;
54         for ( int i = 1; i <= M; i++ )
55             for ( int j = 1; j <= N; j++ )
56             {
57                 scanf( "%d", &x );
58                 if (!x)                
59                     map[i] += (1<<(j-1));    //每次改变一位二进制数字，且1代表该位置不能放牧(方便判断)
60             }
61 
62         for ( int i = 0; i < top; i++ )
63             if (fit(1, i))
64                 dp[1][i] = 1;
65 
66         for ( int i = 2; i <= M; i++ )
67             for ( int j = 0; j < top; j++ )
68             {
69                 if (!fit(i,j))    continue;
70                 for ( int k = 0; k < top; k++ )
71                 {
72                     if (!fit(i - 1, k)) continue;
73                     if (!(stage[j]&stage[k]))
74                         dp[i][j] += dp[i-1][k];
75                 }
76             }
77         int ans = 0;
78         for ( int i = 0; i < top; i++ )
79             { ans += dp[M][i]; ans %= mod; }
80         printf( "%d", ans );
81     }
82 
83     return 0;
84 }
View Code

 萌新第二题：POJ1185 本来不难的题，结果遇到了一个语言底层的神秘bug！！！！！调试了4个小时以上才发现是g数组才开了15个，可是g数组作为全局变量的时候并没有越界报错！？甚至输了超过N组数据程序能够在底层把N修改了？？？？太神秘了

  1 #include <iostream>
  2 #include <string.h>
  3 #include <cstdio>
  4 #include <queue>
  5 #include <math.h>
  6 #include <string>
  7 #include <algorithm>
  8 #define SIGMA_SIZE 26
  9 #pragma warning ( disable : 4996 )
 10 
 11 using namespace std;
 12 typedef long long LL;
 13 
 14 inline int Max(int a,int b) { return a>b?a:b; }
 15 inline int Min(int a,int b) { return a>b?b:a; }
 16 inline int gcd( int a, int b ) { return b==0?a:gcd(b,a%b); }
 17 inline int lcm( int a, int b ) { return a/gcd(a,b)*b; }  //a*b = gcd*lcm
 18 const int inf = 0x3f3f3f3f;
 19 const int maxn = 102;
 20 const int maxk = 200;
 21 const int mod = 100000000;
 22 
 23 char str[15];
 24 int stage[maxk], g[maxn], num[maxk];
 25 int dp[maxn][maxk][maxk];
 26 
 27 inline bool ok(int x)
 28 { if ( (x&(x<<1))!=0 || (x&(x<<2))!=0 ) return false; return true; }        //相容返回true
 29 
 30 inline bool check( int i, int j )        //相容返回true
 31 { return !(g[i]&stage[j]); }
 32 
 33 int main()
 34 {
 35     int ans = 0;
 36     int N, M, top;
 37     while (~scanf("%d %d", &N, &M))
 38     {
 39         //ReadAndInit();
 40 
 41         for (int i = 1; i <= N; i++)
 42         {
 43             scanf("%s", str);
 44             for (int j = 0; j < M; j++)
 45                 if ( str[j] == 'H' )
 46                     g[i] += (1<<j);
 47         }
 48 
 49         top = 0;
 50         int tot = 1<<M;
 51         for ( int i = 0; i < tot; i++ )
 52             if (ok(i))
 53             {
 54                 stage[top] = i;
 55                 int cnt= 0, tmp = i;
 56                 while(tmp)
 57                 { cnt++; tmp = tmp&(tmp-1); }
 58                 num[top++] = cnt;
 59             }
 60 
 61         //if(n==1)
 62         for ( int i = 0; i < top; i++ )
 63             if ( check(1, i) )
 64             {
 65                 dp[1][i][0] = num[i];
 66                 ans = max(ans, dp[1][i][0]);
 67             }
 68         if (N==1) break;
 69 
 70 
 71         for ( int i = 0; i < top; i++ )
 72         {
 73             if (!check(2,i)) continue;
 74             for ( int j = 0; j < top; j++ )
 75                 if ( check(1,j) )
 76                 {
 77                     if (stage[i]&stage[j]) continue;
 78 
 79                     dp[2][i][j] = num[i]+num[j];
 80                     ans = max(ans,dp[2][i][j]);
 81                 }
 82         }
 83         if(N==2) break;
 84 
 85 
 86         for ( int i = 3; i <= N; i++ )
 87             for ( int j = 0; j < top; j++ )
 88                 if ( check(i, j) )
 89                     for ( int a = 0; a < top; a++ )
 90                         if ( check(i-1, a) && !(stage[j]&stage[a]) )
 91                             for ( int b = 0; b < top; b++ )
 92                                 if ( check(i-2, b) && !(stage[j]&stage[b])
 93                                     && !(stage[b]&stage[a]) )
 94                                 {
 95                                     dp[i][j][a] = max(dp[i-1][a][b]+num[j], dp[i][j][a]);
 96                                     ans = max(dp[i][j][a],ans);
 97                                 }
 98         break;
 99     }
100     printf("%d
",ans);
101     return 0;
102 }
View Code

相关推荐