原题链接

考察:状压dp

这个是AcWing 1064. 小国王那道题的扩展

思路:

       这道题与小国王的区别在于前两行影响当前行.并且这道题我们求的是炮的最大数量.有几点必须说明:

1. 不能效仿小国王开dp数组f[i,i行状态],如果这样写状态转移方程就是f[i,j] = f[i-2,k]+cnt[j]+cnt[k],枚举i行、i-1、i-2行状态,当它们不在同一列且与地图符合就递推;看上去确实符合逻辑,但是注意这样就不能保证i-1行能够与i-3行匹配.如数据:4 1 P H P H这样输出就与答案不符. 但也不能写成f[i,j] = f[i-1,k]+cnt[j].因为f[i-1,k]保存的是i-1,i-2,i-3的最优解.而在第i行时,i-2行与f[i-1,k]的i-2行可能不是同一行.
2. 答案最后是求最值,所以不要累加...
3. 关于代码为什么不检验p与mp[i-2]:因为答案只会记录到匹配的i、i-1行.也就是说不匹配的一直为0.更何况i-2行是先被计算的.

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cstdio>
 5 #include <vector>
 6 using namespace std;
 7 const int N = 110,M = 11;
 8 char s[N][M];
 9 int mp[N],n,m,f[2][1<<M][1<<M];
10 vector<int> v;
11 int Getcnt(int x)
12 {
13     int cnt = 0;
14     while(x) cnt+=x%2,x/=2;
15     return cnt; 
16 }
17 void Change()
18 {
19     for(int i=1;i<=n;i++)
20       for(int j=0;j<m;j++)
21         if(s[i][j]=='P') mp[i]|=(1<<(m-j-1));
22     for(int i=0;i<1<<m;i++)
23     {
24         bool ok = 1;
25         for(int j=0;j<m;j++)
26         {
27             if((i>>j&1)&&(i>>(j+1)&1)) ok = 0;
28             if((i>>j&1)&&(i>>(j+2)&1)) ok = 0;
29             if(!ok) break;
30         }
31         if(ok) v.push_back(i);
32     }
33 }
34 int main() 
35 {
36     int ans = 0;
37     scanf("%d%d",&n,&m);
38     for(int i=1;i<=n;i++) scanf("%s",s[i]);
39     Change();
40     for(int i=1;i<=n;i++)
41       for(int j=0;j<v.size();j++)
42         for(int k=0;k<v.size();k++)
43           if(((v[j]&v[k])==0)&&((v[j]|mp[i])==mp[i])&&((v[k]|mp[i-1])==mp[i-1]))
44             for(int p=0;p<v.size();p++)
45               if((v[k]&v[p])==0&&(v[p]&v[j])==0)
46               {
47                    int a = v[j],b = v[k],c = v[p];
48                    f[i&1][a][b] = max(f[i-1&1][b][c]+Getcnt(a),f[i&1][a][b]);
49               }
50     for(int i=0;i<v.size();i++)
51       for(int j=0;j<v.size();j++) ans =max(f[n&1][v[i]][v[j]],ans);
52     printf("%d\n",ans);
53     return 0;
54 }