NOI2001 炮兵阵地

炮兵阵地"/>

NOI2001 炮兵阵地

状压金典

dp[i][j][k]表示第i行状态为j，且上一行状态为k的最多放置的炮兵数
优化1：预处理出每行的可能状态

具体看程序了！！！
AC代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#define N 107
#define M 1024
using namespace std;int a[N],k=0,v[67],num[M];int dp[2][M][M];//滚动数组 
void find(int x){//统计当前可行状态的数值 
    int ans=0,f=1;while(f<=x){
        if((f&x)!=0)ans++;f=f<<1;
    }num[x]=ans;
}
void ycl(int c){//预处理出当前m的每行的二进制可能的状态 
    int f=0;while(f<=((1<<c)-1)){
        if((f&(f<<1))==0&&(f&(f<<2))==0){
            k++;v[k]=f;find(f);
        }f++;
    }
}
int main(){
    int i,j,n,m;
    scanf("%d%d",&n,&m);
    for(i=1;i<