[P2704][NOI2001]炮兵阵地 (状态压缩)

最近抄状压的代码……

然后盯上了这个题目

调试了一个晚上，终于A了

但是是对着宝典打的，我依然不懂状态压缩

那么下一步先把装压放一放，学一下树形DP吧

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<queue>

#include<stack>

#include<cstring>

#include<string>

using namespace std;

int n,m,s[][];

int f[][][];

int num[][];

bool map[][];

int getnum(int x)

{

    int t=;

    while(x>){

        x=x&(x-);

        t++;

    }

    return t;

}

void dp(){

    s[][]=;

    int s1,s2,m=;

    for(int i=;i<=n;i++,m=m^)

    for(int a=;a<=s[i-][];a++){

        s1=s[i-][a];

        for(int b=;b<=s[i][];b++)

        if(map[s1][s[i][b]]){

            s2=s[i][b];

            if(i==) f[m][a][b]=max(f[m][a][b],num[i][b]);

            else{

                for(int c=;c<=s[i-][];c++)

                if(map[s[i-][c]][s1] && map[s[i-][c]][s2])

                f[m][a][b]=max(f[m][a][b],f[m^][c][a]+num[i][b]);

            }

        }

    }

    int ans=;

    m=m^;

    for(int a=;a<=s[n-][];a++)

    for(int b=;b<=s[n][];b++)

    ans=max(ans,f[m][a][b]);

    cout<<ans;

}

int main()

{

    int q;cin>>n>>m;

    string tmp;

    for(int i=;i<=n;i++)

    {

        cin>>tmp;

        q=;

        for(int j=;j<tmp.size();j++){

            if(tmp[j]=='P') q=(q<<);

            else q=(q<<)|;

        }

        for(int j=;j<(<<m);j++){

            if((j<<)&j || (j<<)&j || (j>>)&j || (j>>)&j) continue;

            if(q&j) continue;

            ++s[i][];

            s[i][s[i][]]=j;

            num[i][s[i][]]=getnum(j);

        }

    }

    for(int i=;i<=(<<m);i++){

        for(int j=;j<=(<<m);j++)

        if(!(i&j)) map[i][j]=true;

    }

    dp();

    return ;

}