状压dp（其一）

· · 个人记录

话说炮兵阵地一题，天下之奇难。复观其许久，实难有就。但见“P”“H”穿与其间，霎时有飞沙走石，雾凇沆砀，飘渺云烟，迷人眼，不见其实。然则和解之有？思索良久，盖如状态压缩一策。 其大意如此：

兵部尚书欲于n乘以m之网图上军炮兵。一n乘以m建之图由淮行遂列为，图之每格可是山（以“H”示），亦可是平原（以“P”示也。，如下图。每于一格平原地最多可置一炮兵（山不能军炮兵。；一炮兵军于地图上之击围若图黑地所示：

若在图中之黑色所标之平原上署一支炮兵军，则图中之黑者网格示其能攻得之地：循横左右各二格，循经上下各二格。图上他白网格均击不至。自图上见炮兵之击不阻者。今日，将规所部炮兵军，以防误伤之先下（保他两支炮兵军间不相攻，即一支炮兵军皆不在他支炮兵军之攻内。，问全图内多能设吾之炮兵军几何？

入出式

入式：

第一行有二由空格分开之方算，分示弱与强；

方之于行，每一行有连者遂一字元（‘P’或‘H’），中无空格。次为图中每一行之数。N<=百；M<=十。

出格：

仅一行，含一算K，示致多能设之炮兵数也。 

#include<bits/stdc++.h>
using namespace std;

const int N = 105;  
int cur[N];  
int dp[N][65][65];  //dp[i][j][k]表示放第i行时，第i行为第j个状态，第i-1行为第k个状态最多可以放多少个炮兵  
int state[N], num[N];  
int n, m, p; 

bool check(int x)
{
    if(x&(x>>1)) return 0;
    if(x&(x>>2)) return 0;
    return 1;
}

int Count(int x)
{
    int i=1,ans=0;
    while(i<=x)
    {
        if(i&x) ans++;
        i<<=1;
    }
    return ans;
}

int init()
{
    p=0;
    memset(state,0,sizeof(state));  
    memset(num,0,sizeof(num));  
    for(int i=0;i<(1<<m);i++)
    {
        if(check(i))
        {
            state[p]=i;
            num[p]=Count(i);
            p++; //p是预备方案数 
        }
    }
}

int main()
{
    char ch;
    scanf("%d%d",&n,&m);
    memset(dp, 0, sizeof(dp));  
    memset(cur, 0, sizeof(cur));  
    for(int i=0;i<n;i++)

    for(int j=0;j<m;j++)
    {
        //scanf("%c",&ch);
        cin>>ch;
        if(ch=='H') 
        {
            cur[i]+=(1<<(m-1-j));
        }
    }

    init();
    for(int i=0;i<p;i++)
    {
        if(!(cur[0]&state[i])) 
        dp[0][i][0]=num[i];
    }
    for(int i=0;i<p;i++)
    {
        if(!(cur[1]&state[i]))
        {
            for(int j=0;j<p;j++)
            {
                if(!(state[i]&state[j]))
                dp[1][i][j]=max(dp[1][i][j],dp[0][j][0]+num[i]);
            }
        }
    }

    for(int v=2;v<n;v++)
    {
        for(int i=0;i<p;i++)
        {
            if(!(state[i]&cur[v]))
            {
                for(int j=0;j<p;j++)
                {
                    if(!(state[j]&cur[v-1]))
                    if(!(state[i]&state[j]))
                    {
                        for(int k=0;k<p;k++)
                        {
                            if(!(state[k]&cur[v-2]))
                            if(!(state[i]&state[k]))
                            if(!(state[j]&state[k]))
                            {
                                dp[v][i][j]=max(dp[v][i][j],dp[v-1][j][k]+num[i]);
                            }
                        }
                    }
                }
            }
        }
    }

    int ans=0;
    for(int i=0;i<p;i++)
    for(int j=0;j<p;j++)
    {
        ans=max(ans,dp[n-1][i][j]);
    }
    printf("%d\n", ans);   
    return 0;  
}

在此谈一谈为何要倒置‘H’,'P'的原因。

设想一下，若1示可占，0示山，则有预备方法（如1010）与地形（如1101），此二者按位与后，结果！=0，但显然，此种匹配不符合要求，因为真为符合，假为不符合，若按照真假去辨别，一定有错。于是想到0示可占，1示山，则只要有一一（1和1）成对 那么便是结果为真，方案不可行；0，0为对，0,1搭配，都为假， 符合。所以只需在判断时判定假为真，真为假即可梳理所有合法状况。