ZJU 3723 状压DP

交一次就A了，自己都不敢相信。。。但愿不是水过去的。。。

这题跟炮兵阵地几乎一样，不同的是炮兵的炮能越过山，可是这里的杨桃打不穿障碍。一个处理的办法就是把当前的状态移一下之后与上障碍状态的反。

例如判断k状态向左打两格会不会打到自己，if(k&(((k<<1)&(~r[i]))<<1)) return false;这样就可以了。还要这题还比炮兵阵地的多了两个放向，但这样也只是多两句代码而已。。。

不熟悉状压DP的建议先做一下炮兵阵地这题

代码如下

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

int dp[2][200][200],s[3][1009],r[1009],cnt[3],num[1<<12],n,m;

int num1(int x) //判断状态x里有几个1
{
    int ans=0;
    while(x>0)
    {
        x&=(x-1);
        ans++;
    }
    return ans;
}

bool can(int k,int i)
{
    if(k&r[i]) return false;    //判断有没有放在障碍上
    if(k&(k<<1)) return false;  //判断向左打一格会不会伤到同一行的自己
    if(k&(((k<<1)&(~r[i]))<<1)) return false;   //判断向左打两格会不会商到同一行的自己，模拟子弹，向左打一格之后与上障碍的非，表示遇到障碍后子弹消失了
    return true;
}

bool can1(int j,int k)  //判断本行的状态j会不会打到上一行的状态k
{
    if(j&k) return false;
    if((j<<1)&k) return false;
    if((j>>1)&k) return false;
    return true;
}

bool can2(int j,int k,int r)    //判断本行的状态j会不会打到上两行的状态k，r表示上一行的障碍的状态
{
    if(k&(j&(~r))) return false;
    if(k&(((j<<1)&(~r))<<1)) return false;
    if(k&(((j>>1)&(~r))>>1)) return false;
    return true;
}

int print(int k,int m=m)    //这个函数调试用的。。。
{
    if(m<=0) return 2;
    print(k>>1,m-1);
    cout<<(k&1);
    if(m==::m) cout<<"       ";
    return 2;
}

void DP()
{
    int i=0,j,k,k1,k2;
    cnt[0]=0;
    for(j=0;j<(1<<m);j++) if(can(j,0)) s[0][cnt[0]++]=j;
    memset(dp,-1,sizeof(dp));
    for(j=0;j<cnt[0];j++)
    {
        dp[0][j][0]=num[s[0][j]];
        //print(s[0][j]);cout<<i<<" "<<dp[0][j][0]<<endl;
    }
    //cout<<endl;
    for(i=1;i<n;i++)
    {
        cnt[i%3]=0;
        for(j=0;j<(1<<m);j++) if(can(j,i)) s[i%3][cnt[i%3]++]=j;
        for(j=0;j<cnt[i%3];j++)
        {
            for(k1=0;k1<cnt[(i-1)%3];k1++) if(can1(s[i%3][j],s[(i-1)%3][k1]))
            {
                if(i>1)
                {
                    for(k2=0;k2<cnt[(i-2)%3];k2++) if(can2(s[i%3][j],s[(i-2)%3][k2],r[i-1]))
                    {
                        if(dp[(i-1)&1][k1][k2]>=0) dp[i&1][j][k1]=max(dp[i&1][j][k1],dp[(i-1)&1][k1][k2]+num[s[i%3][j]]);
                    //print(s[i%3][j]);print(s[(i-1)%3][k1]);print(s[(i-2)%3][k2]);cout<<i<<" "<<dp[i&1][j][k1]<<endl;
                    }
                }
                else if(dp[(i-1)&1][k1][0]>=0) dp[i&1][j][k1]=max(dp[i&1][j][k1],dp[(i-1)&1][k1][0]+num[s[i%3][j]]);
            }
        }
        //cout<<endl;
    }
}

int main()
{
    //freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);
    for(int i=0;i<(1<<12);i++) num[i]=num1(i);
    while(cin>>n>>m)
    {
        if(n==0 && m==0) return 0;
        int i,j,k;
        char c;
        for(i=0;i<n;i++)
        {
            r[i]=0;
            for(j=0;j<m;j++)
            {
                cin>>c;
                r[i]<<=1;
                if(c==‘X‘) r[i]|=1;
            }
        }
        DP();
        int ans=0;
        i=n-1;
        for(j=0;j<cnt[i%3];j++) for(k=0;k<cnt[(i-1)%3];k++) ans=max(ans,dp[i&1][j][k]);
        cout<<ans<<endl;
    }
    return 0;
}

别人写的另一个题解：

http://blog.csdn.net/just_water/article/details/9832761

ZJU 3723 状压DP,布布扣,bubuko.com

ZJU 3723 状压DP

原文：http://blog.csdn.net/w750636248/article/details/20000533