POJ1185 炮兵阵地

题目传送门

中文题面还是很清楚的。

不想解释题面了。

NOI原题确实是很难的。

因为第$i$行的状态与前$2$行的状态有关，所以我们可以记下当前行的状态和上一行的状态方便转移。

设$f[i][j][k]$表示前$i$行，第$i$行的状态是$j$，第$i-1$行的状态是$k$，总共可以放炮兵部队的支数。

还是很好转移的。

但是直接做的复杂度为$O(n{2}^{3m})$，完全无法接受。

对于一个状态$j$，如果$j$的第$i$位是$1$，则$j$的第$i+$1\mathrm{位}\mathrm{和}\mathrm{第}$i+2$位不能为1。（设这个条件为条件1）

第$i-1$位和第$i-2$位不用考虑（因为如果这两位中有$1$，则不满足上面的条件）

因为$m$的最大值是$10$，所以在$[0,2^{10})$强行找出所有满足上面条件的状态$j$（满足$j\mathrm{\&}(j<<1)=0$ 且的j）

发现在$[0,2^{10})$只有60个满足条件的$j$。

给每个$j$一个序号。

设$f[i][j][k]$表示前$i$行，第$i$行是第$j$个满足条件$1$的状态，第$i-1$行是第$k$个.....，总共可以放炮兵部队的支数。

然后转移就好。

注意对于$\ge 2^m$的$j$，同样不符条件。

复杂度$O(n\ast {60}^3)$

/*
Author: CNYALI_LK
LANG: C++
PROG: poj1185.cpp
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define up(a,b,c) for (int a(b),end##a(c);a<=end##a;++a)
#define down(a,c,b) for (int a(b),end##a(c);a>=end##a;--a)
#define uup(a,c,b) for (int a(b),end##a(c);a<=end##a;++a)
#define udown(a,b,c) for (int a(b),end##a(c);a>=end##a;--a)
#define go(a,b) for(int a=0;a<b;++a)
#define endl '\n'
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
struct inout{
//IO优化省略
};
inout io;
template<class T>void chkmin(T &a,T b){a=a<b?a:b;}
template<class T>void chkmax(T &a,T b){a=a>b?a:b;}
const int N=100;
const int M=1<<10;
char s[N+2];
int a[N];
int sb[66];
int f[N][64][64],sz[64];
int chk(int x){
    return !(x&(x<<1)||x&(x<<2));
}
int lowbit(int x){
    return x&-x;
}
int count(int x){
    int t=0;
    while(x){x-=lowbit(x);++t;}
    return t;
}
int main(){
#ifdef cnyali_lk
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    io.init();
    int n,m,yyc=0;
    io>>n>>m;
    go(i,M)if(chk(i)){sb[yyc]=i;sz[yyc]=count(i);++yyc;
    }
    go(i,n){
        io>>s;
        go(j,m){
            if(s[j]=='H')a[i]|=1<<j;//每一行的山地的状态
        }
    }
    int t=1<<m;
    sb[yyc]=2333;
    ++yyc;
    go(i,yyc)if(sb[i]>=t){t=i;break;}
//  printf("%")
    go(i,n)go(j,t){
        if(sb[j]&a[i])continue;//如果这个状态不能放在第i行就换一个。
        if(i==0){f[i][j][0]=sz[j];}//第一行直接做
        else if(i==1){
            go(k,t)if(sb[k]&a[i-1]||sb[k]&sb[j])continue;else f[i][j][k]=f[i-1][k][0]+sz[j];;//第二行乱搞
        }
        else{
            go(k,t)if(sb[k]&a[i-1]||sb[k]&sb[j])continue;else{
                go(l,t)if(sb[l]&a[i-2]||sb[l]&sb[k]||sb[l]&sb[j])continue;
                else chkmax(f[i][j][k],f[i-1][k][l]);
                f[i][j][k]+=sz[j];
            }
        }
    }
    int ans=0;
    if(n==1){
        go(i,t)chkmax(ans,f[n-1][i][0]);
    }
    else go(i,t)if(sb[i]&a[n-1])continue;else go(j,t)if(sb[j]&a[n-2]||sb[j]&sb[i])continue;else chkmax(ans,f[n-1][i][j]);
//  up(i,1,n-1)go(j,t)go(k,t)if(!(sb[j]&a[i]||sb[k]&a[i-1]||sb[j]&sb[k])){printf("%d %d %d %d\n",i,j,k,f[i][j][k]);}
    io<<ans<<endl;
    io.out();
    return 0;
}