POJ1185 炮兵阵地
中文题面还是很清楚的。
不想解释题面了。
NOI原题确实是很难的。
因为第\(i\)行的状态与前\(2\)行的状态有关，所以我们可以记下当前行的状态和上一行的状态方便转移。
设\(f[i][j][k]\)表示前\(i\)行，第\(i\)行的状态是\(j\)，第\(i-1\)行的状态是\(k\)，总共可以放炮兵部队的支数。
还是很好转移的。
但是直接做的复杂度为\(O(n2^{3m})\)，完全无法接受。
对于一个状态\(j\)，如果\(j\)的第\(i\)位是\(1\)，则\(j\)的第$i+\(1位和第\)i+2$位不能为1。（设这个条件为条件1）
第\(i-1\)位和第\(i-2\)位不用考虑（因为如果这两位中有\(1\)，则不满足上面的条件）
因为\(m\)的最大值是\(10\)，所以在\([0,2^{10})\)强行找出所有满足上面条件的状态\(j\)（满足\(j\&(j<<1) = 0\) 且$ j&(j<<2)=0$的j）
发现在\([0,2^{10})\)只有60个满足条件的\(j\)。
给每个\(j\)一个序号。
设\(f[i][j][k]\)表示前\(i\)行，第\(i\)行是第\(j\)个满足条件\(1\)的状态，第\(i-1\)行是第\(k\)个.....，总共可以放炮兵部队的支数。
然后转移就好。
注意对于\(\ge2^m\)的\(j\)，同样不符条件。
复杂度\(O(n*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;
}