题解 P2704 【[NOI2001]炮兵阵地】

中二病 · 2019-02-03 21:10:54 · 题解

状压DP

dp[i][j][k],i表示行数，j表示这一行状态，k表示上一行状态（因为一行要受上两行的影响，压掉一个后还要表示上一行的状态）

具体的细节看注释

混合运算加括号！

混合运算加括号！！

混合运算加括号！！！

被卡了一晚上

很喜欢我写的代码（逃）

上代码

#include<iostream>
#include<cstdio>
#include<cstring> 
using namespace std;
int n,m,dp[110][1<<10][1<<10],tot,zy[1<<10],a[110],num[1<<10],ans;
char ch;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>ch;
            if(ch=='H')a[i]+=1<<(j-1);//把每一行转成二进制状态 
        }
    }
    int nn=(1<<m)-1;//状态的最大值，加括号！！！再这卡了一晚上 
    for(int i=0;i<=nn;i++)
    {
        if(!(i&(i<<1))&&!(i&i<<2))//状态左右两格互不影响 
        {
            tot++;
            zy[tot]=i;//存状态 
            int pg=i;
            while(pg>0)
            {
                if(pg&1)num[tot]++;//存状态中炮兵的数量 
                pg>>=1;
            }
        }
    }
    //预处理第二行 
    for(int i=1;i<=tot;i++)
    {
        for(int j=1;j<=tot;j++)
        {
            if(!(zy[i]&zy[j])&&!(zy[i]&a[2])&&!(zy[j]&a[1]))//互不影响且不在山上 
            {
                dp[2][i][j]=num[j]+num[i];
            }
        }
    }
    for(int i=3;i<=n;i++)//枚举行 
    {
        for(int j=1;j<=tot;j++)//本行 状态 
        {
            if(!(zy[j]&a[i]))//不在山上 
            {
                for(int k=1;k<=tot;k++)//上一行状态 
                {
                    if(!(zy[k]&a[i-1])&&!(zy[k]&zy[j]))//不在山上，不与本行冲突 
                    {
                        for(int p=1;p<=tot;p++)//上两行状态 
                        {
                            if(!(zy[p]&a[i-2])&&!(zy[p]&zy[k])&&!(zy[p]&zy[j]))//不在山上，不冲突 
                            {
                                dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][p]+num[j]);//转移方程 
                                ans=max(ans,dp[i][j][k]);//转移答案 
                            }
                        }
                    }
                }
            }
        }
    }
    cout<<ans;
    return 0;
}