//初学状压DP，感觉比较诡异吧，看了题解才懂

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int mp[110],f[2][1050][1050],m,n;
int d[1050],mi[1050],tot,ans;
int num[110][1050],nm[110];
inline bool check(int x)
{
    if((x&(x<<1))) return 0;
    if((x&(x<<2))) return 0;
    if((x&(x>>1))) return 0;    //判断横向是否符合条件
    if((x&(x>>2))) return 0;
    return 1;   
}
inline bool check2(int x,int y)
{
    int a=mp[x],b=d[y];
    for(int i=0;i<m;++i)
     if(b&(1<<i)) 
      if(!(a&(1<<i))) return 0;  //判断是否符合地形
    return 1;
}
inline int count(int x)
{
    int sum=0;
    for(int i=0;i<m;++i)
     if(x&(1<<i)) sum++;   //统计该状态下的炮兵数量
    return sum;
}
inline bool pd(int x,int y)
{
    if(d[x]&d[y]) return 0;  //判断是否与之前的行矛盾
    return 1; 
}
int main()
{
    int i,j;
    scanf("%d%d\n",&n,&m);
    for(i=1;i<=n;++i)
     {
        char s[15];
        gets(s);
        for(j=0;j<m;++j) 
         if(s[j]=='P') mp[i]+=(1<<j);
     }
    int N=1<<m;
    for(i=0;i<N;++i)
     if(check(i)) d[++tot]=i,mi[tot]=count(i);
    if(n==1)
     {
        int maxn=mi[1];
        for(i=2;i<=tot;++i)
         if(check2(1,i)&&mi[i]>maxn) maxn=mi[i];
        printf("%d\n",maxn);
        return 0;
     }
    for(i=1;i<=n;++i)
     for(j=1;j<=tot;++j)
      if(check2(i,j)) num[i][++nm[i]]=j;
    for(i=1;i<=nm[1];++i)
      for(j=1;j<=nm[2];++j)
       if(pd(num[1][i],num[2][j]))
         f[0][j][i]=max(f[0][j][i],mi[num[1][i]]+mi[num[2][j]]);
    for(i=3;i<=n;++i)
     {
        int t=i%2,t1=(i-1)%2;
        for(j=1;j<=nm[i];++j)
         for(int k=1;k<=nm[i-1];++k)
          if(pd(num[i][j],num[i-1][k]))
           for(int h=1;h<=nm[i-2];++h)
            if(pd(num[i-1][k],num[i-2][h])&&pd(num[i][j],num[i-2][h]))
                f[t][j][k]=max(f[t][j][k],f[t1][k][h]+mi[num[i][j]]);
        memset(f[t1],0,sizeof(f[t1]));
     }
    int t=n%2;
    for(i=1;i<=nm[n];++i)
      for(j=1;j<=nm[n-1];++j)
       if(pd(num[n][i],num[n-1][j]))
        ans=max(ans,f[t][i][j]);
    printf("%d\n",ans);
    return 0;
}
//另外直接把两行压成一维是做不出来的，至少极不好做

#include<iostream>
#include<string>
#include<set>
#include<map>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<cstring>
using namespace std;
const int inf=0x3f3f3f3f;
typedef long long LL;


int n,m;
char mmp[105][20];
int dp[105][100][100];
int num[100],state[100],dat[105];
int tot;
void init()
{
    for(int i=1;i<=n;i++)
    {
        scanf("%s",mmp[i]+1);
        for(int j=1;j<=m;j++)
        {
            if(mmp[i][j]=='H')dat[i]|=(1<<(m-j));
        }
    }
    tot=0;
    for(int i=0;i<(1<<m);i++)
    {
        int nx=i;
        int cnt=0;
        if(  (i>>1)&i || (i>>2)&i )continue;
        while(nx)
        {
            if(nx&1)cnt++;
            nx>>=1;
        }
        state[tot]=i;
        num[tot++]=cnt;
    }
    return ;
}
int main()
{
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        memset(num,0,sizeof(num));
        memset(state,0,sizeof(state));
        memset(dat,0,sizeof(dat));
        init();
        int ans=0;
        for(int i=0;i<tot;i++)
        {
            if(state[i]&dat[1])continue;
            dp[1][i][0]=num[i];
            ans=max(ans,dp[1][i][0]);
        }
        if(n==1)
        {
            printf("%d\n",ans);
            continue;
        }
        for(int i=0;i<tot;i++)
        {
            if(state[i]&dat[2])continue;
            for(int j=0;j<tot;j++)
            {
                if(state[i]&state[j])continue;
                dp[2][i][j]=max(dp[2][i][j],dp[1][j][0]+num[i]);
                ans=max(ans,dp[2][i][j]);
            }
        }
        if(n==2)
        {
            printf("%d\n",ans);
            continue;
        }
        for(int i=3;i<=n;i++)
        {
            for(int j=0;j<tot;j++)
            {
                if(state[j]&dat[i])continue;
                for(int k=0;k<tot;k++)
                {
                    if(state[j]&state[k])continue;
                    for(int q=0;q<tot;q++)
                    {
                        if(state[j]&state[q])continue;
                        dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][q]+num[j]);
                        ans=max(ans,dp[i][j][k]);
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

//
//  main.cpp
//  algorithm
//
//  Created by apple on 2018/9/25.
//  Copyright © 2018 apple. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <set>

#define MAXN 100
#define MAXM 10
#define INF 999999999

using namespace std;

int n, m;
int matrix[MAXN];
short int dp[MAXN][1 << MAXM][1 << MAXM];
short int cnt[1 << MAXM];
short int possible[1 << MAXM], psize = 0;

void input(){
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        string s0;
        cin >> s0;
        for(int j = 0; j < m; j++){
            if(s0[j] == 'H') matrix[i] |= (1 << j);
        }
    }
}

void init(){
    memset(dp, -1, sizeof(dp));
    for(short i = 0; i < (1 << MAXM); i++){
        short tt = 0, x = i;
        while(x > 0){
            tt += (x & 1);
            x >>= 1;
        }
        cnt[i] = tt;
    }
    for(short i = 0; i < (1 << MAXM); i++){
        short x = i, last = -1, pos = 0, flag = true;
        while(x > 0){
            if(((x & 1) == 1) && (last != -1) && (pos - last <= 2)){flag = false; break;}
            if((x & 1) == 1) last = pos;
            pos++;
            x >>= 1;
        }
        if(flag) possible[psize++] = i;
    }
}

short int max(short int a, short int b){
    return (a > b)? a: b;
}

short int solve(int r, short used1, short used2){
    if(r == n) return 0;
    if(~dp[r][used1][used2]) return dp[r][used1][used2];
    short sup = (1 << m) - 1 - (matrix[r] | used1 | used2), opt = 0;
    for(int i = 0; i < psize; i++){
        if((possible[i] | sup) == sup) opt = max(opt, solve(r + 1, possible[i], used1) + cnt[possible[i]]);
    }
    return dp[r][used1][used2] = opt;
}

int main(int argc, const char * argv[]) {
    input();
    init();
    short int ans = solve(0, 0, 0);
    cout << ans << endl;
    return 0;
}

写记忆化, short险过

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m,sta_size;
int a[100];
int sta[(1<<10)];
int num[(1<<10)];
int f[2][(1<<10)][(1<<10)];

int main()
{
    while (~scanf("%d%d",&n,&m))
    {
        memset(a,0,sizeof(a));
        memset(sta,0,sizeof(sta));
        memset(num,0,sizeof(num));
        memset(f,0,sizeof(f));
        for (int i=0;i<n;i++)
        {
            char temp=getchar();
            for (int j=0;j<m;j++)
            {
                char temp;
                scanf("%c",&temp);
                a[i]=(a[i]|((temp=='H')?(1<<j):0));
            }
        }
        sta_size=0;
        for (int i=0;i<(1<<m);i++)
            if ((i&(i>>1))==0&&((i&(i>>2))==0))
            {
                sta[sta_size]=i;
                int sum=0;
                for (int j=0;j<10;j++)
                    sum+=(((i&(1<<j))!=0)?1:0);
                num[sta_size]=sum;
                sta_size++;
            }
        int now=0,ans=0;
        for (int i=0;i<sta_size;i++)
        {
            if ((a[0]&sta[i])==0)
            {
                f[now][i][0]=num[i];
                ans=max(ans,f[now][i][0]);
            }
        }
        if (n==1)
        {
            printf("%d\n",ans);
            continue;
        }
        now^=1;
        for (int i=0;i<sta_size;i++)
        {
            if ((a[1]&sta[i])==0)
                for (int j=0;j<sta_size;j++)
                    if ((sta[i]&sta[j])==0)
                    {
                        f[now][i][j]=max(f[now][i][j],f[now^1][j][0]+num[i]);
                        ans=max(ans,f[now][i][j]);
                    }
        }
        now^=1;
        if (n==2)
        {
            printf("%d\n",ans);
            continue;
        }
        for (int x=2;x<n;x++,now^=1)
            for (int i=0;i<sta_size;i++)
                if ((a[x]&sta[i])==0)
                    for (int j=0;j<sta_size;j++)
                        if ((a[x-1]&sta[j])==0&&(sta[i]&sta[j])==0)
                            for (int k=0;k<sta_size;k++)
                                if ((a[x-2]&sta[k])==0&&(sta[i]&sta[k])==0&&(sta[j]&sta[k])==0)
                                {
                                    f[now][i][j]=max(f[now][i][j],f[now^1][j][k]+num[i]);
                                    ans=max(ans,f[now][i][j]);
                                }
        printf("%d\n",ans);
    }
}

位运算一定要加括号！！！！！！！！！！！！！！！！！！
位运算一定要加括号！！！！！！！！！！！！！！！！！！
位运算一定要加括号！！！！！！！！！！！！！！！！！！
这个题改的都疯了
```C++
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#define maxn (1000 + 20)
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
using namespace std;
typedef long long int LLI;

int a[maxn],n,m;
int gts[20],state[100],cnt = 0;
int counts[100];
int dp[maxn][100][100];

void dfs(int last,int p,int c) {
if(p >= m) {
int s = 0;
for(int i = 0; i < m; i ++) s = s * 2 + gts[i];
// for(int i = 0; i < m; i ++) printf("%d ",gts[i]);
// printf(" %d\n",c);
counts[cnt] = c;
state[cnt ++] = s;
return;
}
if(p - last > 2) {
gts[p] = 1;
dfs(p,p + 1,c + 1);
gts[p] = 0;
dfs(last,p + 1,c);
} else {
gts[p] = 0;
dfs(last, p + 1,c);
}
}

int main() {
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%d%d",&n,&m);
getchar();
for(int i = 1; i <= n; i ++) {
a[i] = 0;
for(int j = 1; j <= m; j ++) {
char temp;
scanf("%c",&temp);
// printf("%c ",temp);
if(temp == 'H') a[i] = a[i] * 2 + 1;
else a[i] = a[i] * 2;
}
// printf("%d %d\n",i,a[i]);
//printf("\n");
getchar();
}
int re = 0;
dfs(-3,0,0);
// 0100
// 0011
// 0000
// 0100
// 0110
// printf("==================%d\n",cnt);
for(int j = 0; j < cnt; j ++) {
// printf("%d ",counts[j]);
if((state[j] & a[1]) == 0) dp[1][j][cnt - 1] = counts[j];
re = max(re,dp[1][j][cnt - 1]);
// printf("(1-%d-%d)%d\n",j,cnt - 1,dp[1][j][cnt - 1]);
}
// printf("\n");
for(int i = 2; i <= n; i ++) {
for(int j = 0; j < cnt; j ++) {
if((state[j] & a[i]) != 0) continue;
for(int k = 0; k < cnt; k ++) {
if((state[k] & state[j]) != 0) continue;
if((state[k] & a[i - 1]) != 0) continue;
for(int l = 0; l < cnt; l ++) {
if((state[l] & state[j]) != 0) continue;
if((state[l] & state[k]) != 0) continue;
if((state[l] & a[i - 2]) != 0) continue;
dp[i][j][k] = max(dp[i - 1][k][l] + counts[j],dp[i][j][k]);
}
re = max(dp[i][j][k],re);
// printf("(%d-%d-%d)%d ",i,j,k,dp[i][j][k]);
}
// printf("\n");
}
// printf("\n");
}
printf("%d\n",re);
return 0;
}
```

状压DP样题。。。然而太久不写都快忘了怎么做了。。。
#include<cstdio>
#include<iostream>
#include<cstring>
#define MAXN 105
using namespace std;

int n,m;

char map[MAXN][15];
int use[MAXN];
int can[MAXN],poi=0;
int num[MAXN];
int f[MAXN][MAXN][MAXN];

inline bool ok(int x)
{
if(x&(x<<1))return false;
if(x&(x<<2))return false;
return true;
}

int cal(int x)
{
int res=0;
while(x)
{
res++;
x&=(x-1);
}return res;
}

inline bool fit(int x,int y)
{return !(x&y);}

void pre()
{
memset(f,-1,sizeof(f));
memset(can,0,sizeof(can));
poi=0;
for(int i=0;i<(1<<m);i++)
if(ok(i))can[poi++]=i;
for(int i=0;i<poi;i++)
{
num[i]=cal(can[i]);
if(fit(use[0],can[i]))
f[0][i][0]=num[i];
}
}

int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=0;i<n;i++)
{
scanf("%s",map[i]);
use[i]=0;
for(int j=0;j<m;j++)
if(map[i][j]=='H')
use[i]|=(1<<j);
}
pre();
for(int i=1;i<n;i++)
for(int j=0;j<poi;j++)
{
if(!fit(use[i],can[j]))continue;
for(int g=0;g<poi;g++)
{
if(!fit(can[j],can[g]))continue;
for(int k=0;k<poi;k++)
{
if((!fit(can[j],can[k]))||f[i-1][g][k]==-1)continue;
f[i][j][g]=max(f[i][j][g],f[i-1][g][k]+num[j]);
}
}
}
int ans=0;
for(int i=0;i<poi;i++)
for(int j=0;j<poi;j++)
ans=max(ans,f[n-1][i][j]);
printf("%d\n",ans);
}

return 0;
}

滚动数组+状态压缩DP，不解释~
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define sz 61
#define G(x) ((x+1)%2+1)
using namespace std;
int f[3][sz][sz],vst[sz],map[101][11],c[sz];
int vnum,n,m;
int st,pst;
void Init(){
char ch;
scanf("%d%d",&n,&m);
scanf("%c",&ch);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%c",&ch);
if (ch=='P') map[i][j]=1;
else map[i][j]=0;
}
scanf("%c",&ch);
}
}
int Check(int x){
int tot=0;
for(int i=0;i<10;i++)
if (x&(1<<i)) tot++;
return tot;
}
void Getvalidstate(){
for(int i=0;i<(1<<m);i++)
if ((!(i&(i<<1)))&&(!(i&(i<<2)))) vst[++vnum]=i,c[vnum]=Check(i);
}
bool Valid(int state,int r){
int rstate=0;
for(int i=1;i<=m;i++)
if (map[r][i])
rstate+=1<<(m-i);
if (!(state&(~rstate))) return true;
return false;
}
void Pretreat(){
for(int i=1;i<=vnum;i++)
if (Valid(vst[i],1)) f[1][i][1]=c[i];
for(int i=1;i<=vnum;i++)
if (Valid(vst[i],2))
for(int j=1;j<=vnum;j++)
if ((!(vst[i]&(vst[j])))&&Valid(vst[j],1))
f[2][i][j]=f[1][j][1]+c[i];
}
int main(){
//freopen("p1.in","r",stdin);
Init();
vnum=0;
Getvalidstate();
memset(f,0,sizeof(f));
Pretreat();
for(int i=3;i<=n;i++){
st=G(i); pst=G(i+1);
for(int j=1;j<=vnum;j++)
if (Valid(vst[j],i))
for(int k=1;k<=vnum;k++)
if (Valid(vst[k],i-1)&&(!(vst[k]&vst[j])))
for(int h=1;h<=vnum;h++)
if ((Valid(vst[h],i-2))&&(!(vst[h]&vst[j]))&&(!(vst[h]&vst[k])))
f[st][j][k]=max(f[st][j][k],f[pst][k][h]+c[j]);
}
int ans=-1;
for(int i=1;i<=vnum;i++)
for(int j=1;j<=vnum;j++)
ans=max(ans,f[st][i][j]);
printf("%d",ans);
return 0;
}

其实为什么二维的DP不行....

f[d][i]表示第d行,状态i.
cnt[d][i] 表示第d行,状态i的炮兵数量.
f[0][i]=cnt[0][i];
f[1][i]=cnt[1][i]+ (i与j冲突?) 0 : cnt[0][j];
对于d>=2,如果i,j,k不冲突则
f[d][i]=max( f[d][i] , f[d-2][k] + cnt[d-1][j] + cnt[d][i] );
否则f[d][i]=max( f[d][i] , cnt[d][i] );

然后只过了两个点....

pascal只写48行你敢信

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 72ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：72ms

20分钟一次水过。。。我现在状态真是好。。。

经典状态压缩动态规划

膜拜hydralisk神牛！

P.S:因为我I,J不分 所以最后找最大值错了2回......

1次AC

先写个辅助程序算出一行中60种可能的排放位置

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 9ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 134ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：143ms

顶礼膜拜hydralisk 神牛！！！！

一次ac,爽!40行程序,题解(+代码):

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

Accepted 有效得分：100 有效耗时：41ms

每一行最多有60种状态

预处理出来后时间就可以压下来了

位运算强大啊！！！

f表示 第i行为j状态 第i-1行为t状态的最优

t,j 为2进制数（状态压缩）

count[j]为 j状态有几个1（就是放了几个）

f=f+count[j]条件(t and j=0)and(k and j=0)and(t and k=0)

数组真是好东西！！！！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 212ms

├ 测试数据 04：答案正确... 166ms

├ 测试数据 05：答案正确... 338ms

├ 测试数据 06：答案正确... 681ms

├ 测试数据 07：答案正确... 681ms

├ 测试数据 08：答案正确... 275ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 1088ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：3441ms

好慢啊！！ 位运算状态压缩的dp ，人家怎么会那么快的呢？

开了2个数组记录状态和状态是否匹配， 状态和山形是否匹配。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 9ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 56ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：65ms

终于AC了，位运算状态压缩的DP真是神奇啊，又长见识了~~

编程时注意shl和shr别搞错了！

好了，做完最后一题，暂时告别vijos了，see you~

膜拜fengyunfly大牛

Accepted 有效得分：100 有效耗时：277ms