POJ

中文题。。

思路：这题可把我恶心坏了，我刚开始的思路其实是正确的。。。

首先我想开个dp[i][s1][s2]保存到 i行为止当前行状态为s1，上一行状态为s2 的最大个数，然后我先把满足行内条件的

状态存起来，空间用滚动数组优化，但是我在写转移方程的时候发现复杂度太大。。。。其实复杂度是够的，因为一行里面

满足行内条件的最多有60个合法状态，哈希一下就好啦，都不用滚动数组。。。

然后我又开脑洞去搞三进制的状态压缩，写到最后发现复杂度又不对，才发现原来的方法是正确的。。。。

  1 #include<cstdio>
  2 #include<vector>
  3 #define fi first
  4 #define se second
  5 #define mk make_pair
  6 #define pii pair<int,int>
  7 #define read(x) scanf("%d",&x)
  8 #define sread(x) scanf("%s",x)
  9 #define dread(x) scanf("%lf",&x)
 10 #define lread(x) scanf("%lld",&x)
 11 using namespace std;
 12 
 13 typedef long long ll;
 14 const int inf=0x3f3f3f3f;
 15 const int INF=0x3f3f3f3f3f3f3f3f;
 16 const int N=107;
 17 const int M=10;
 18 const int mod=1e8;
 19 
 20 int n,m,dp[101][70][70],f[N];
 21 char s[20];
 22 vector<int> v,num;
 23 bool check(int x)
 24 {
 25     int cnt=2,cur=x;
 26     while(x)
 27     {
 28         int now=x%2;
 29         if(cnt<2 && now)
 30             return false;
 31         if(now) cnt=0;
 32         else cnt++;
 33         x/=2;
 34     }
 35     return true;
 36 }
 37 int cal(int x)
 38 {
 39     int ans=0;
 40     while(x)
 41         x-=x&-x,ans++;
 42     return ans;
 43 }
 44 int main()
 45 {
 46     read(n); read(m);
 47     for(int i=0;i<n;i++)
 48     {
 49         scanf("%s",s);
 50         for(int j=0;j<m;j++)
 51             f[i]*=2,f[i]+=s[j]=='P'? 1:0;
 52     }
 53     int up=1<<m;
 54     for(int i=0;i<up;i++)
 55     {
 56         if(check(i))
 57         {
 58             v.push_back(i);
 59             num.push_back(cal(i));
 60         }
 61     }
 62     int sz=v.size();
 63     for(int i=0;i<sz;i++)
 64     {
 65         int s1=v[i];
 66         if((s1|f[0])!=f[0])
 67             continue;
 68         for(int j=0;j<sz;j++)
 69         {
 70             int s2=v[j];
 71             if((s2|f[1])!=f[1] || (s1&s2))
 72                 continue;
 73             dp[1][i][j]=num[i]+num[j];
 74         }
 75     }
 76     for(int i=2;i<n;i++)
 77     {
 78         for(int j=0;j<sz;j++)
 79         {
 80             for(int k=0;k<sz;k++)
 81             {
 82                 for(int u=0;u<sz;u++)
 83                 {
 84                     int s1=v[j],s2=v[k],s3=v[u];
 85                     if((s1&s2) || (s1&s3) || (s1|f[i])!=f[i])
 86                         continue;
 87                     dp[i][k][j]=max(dp[i][k][j],dp[i-1][u][k]+num[j]);
 88                 }
 89             }
 90         }
 91     }
 92     int ans=0;
 93     if(n!=1)
 94     {
 95         for(int i=0;i<sz;i++)
 96             for(int j=0;j<sz;j++)
 97                 ans=max(ans,dp[n-1][i][j]);
 98     }
 99     else
100     {
101         for(int i=0;i<sz;i++)
102             if((v[i]|f[0])==f[0])
103                 ans=max(ans,num[i]);
104     }
105     printf("%d
",ans);
106 }
107 /*
108 */