LianLianKan HDU - 4272 状压dp

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<iostream>
 4 #include<algorithm>
 5 typedef long long ll;
 6 using namespace std;
 7 const int maxn=1005;
 8 const int M=1<<9;
 9 int v[maxn],dp[maxn][1<<9];
10 int main()
11 {
12     int n;
13     while(~scanf("%d",&n))
14     {
15         memset(dp,0,sizeof(dp));
16         for(int i=n;i>0;--i)
17             scanf("%d",&v[i]);
18         dp[0][0]=1;
19         for(int i=1;i<=n;++i)
20         {
21             for(int j=0;j<M;++j)
22             {
23                 if(dp[i-1][j]) //因为题目说明要先抵消栈顶的元素，所以每一次寻找都要找到上一个元素被抵消的位置
24                 {
25                     if(j&1) //这个判断是用来判断这个位置的数字是不是被它上一个位置消掉了
26                     {
27                         dp[i][j>>1]=1;  //因为j这个状态压缩的是它下面10个位置的状态，所以j>>1就完了
28                     }
29                     else
30                     {
31                         int t=0; //记录这个位置实际上下沉了几个位置
32                         for(int k=1;k<=8;++k)
33                         {
34                             if(!(j&(1<<k)) && k-t<=5 && v[i]==v[i+k])
35                             {
36                                 dp[i][(j>>1)|(1<<(k-1))]=1;
37                             }
38                             else if(j&(1<<k))
39                                 t++;
40                         }
41                     }
42                 }
43             }
44         }
45         if(dp[n][0]==1)
46             printf("1\n");
47         else printf("0\n");
48     }
49     return 0;
50 }