卡死在这的第8天

RT

求助

P2704 炮兵阵地

#include <bits/stdc++.h>

using namespace std;

int s[1025];
int sum[1025];
int mp[101];
int dp[101][1025];
int m;

inline char gc()
{
    char p=getchar();
    while(p!=('P')&&p!=('H')) p=getchar();
    return p;
}

inline int get(int x)
{
    int ans=0,i;
    for(i=0;i<=11;++i)
        if((1<<i)&x) ++ans;
    return ans;
}

inline void print(int x)
{
    while(x)
    {
        printf("%d",x&1);
        x>>=1;
    }
    printf("\n");
    return;
}

int main()
{
    char ch;
    int n,tot,cnt=0,ans=0;
    int i,j,k,l;
    scanf("%d%d",&n,&m);
    tot=1<<m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            ch=gc();
            if(ch=='H') mp[i]=mp[i]|(1<<(j-1));
        }
    for(i=0;i<tot;i++)
        if(!((i<<1)&i)&&!((i<<2)&i))
        {
            s[++cnt]=i;
            sum[cnt]=get(i);
        }
    for(i=1;i<=cnt;i++)
        if(!(mp[1]&s[i])) dp[1][s[i]]=sum[i];
    for(i=1;i<=cnt;i++)
        if(!(mp[2]&s[i]))
            for(j=1;j<=cnt;j++)
                if(!(mp[1]&s[j])&&!(s[i]&s[j]))
                    dp[2][s[i]]=max(dp[2][s[i]],dp[1][s[j]]+sum[i]);
    for(i=3;i<=n;i++)
        for(j=1;j<=cnt;j++)
            if(!(mp[i]&s[j]))
                for(k=1;k<=cnt;k++)
                    if(!(mp[i-1]&s[k])&&!(s[j]&s[k]))
                        for(l=1;l<=cnt;l++)
                            if(!(mp[i-2]&s[l])&&!(s[k]&s[l])&&!(s[j]&s[l]))
                                dp[i][s[j]]=max(dp[i][s[j]],sum[k]+dp[i-2][s[l]]+sum[j]);
    for(i=1;i<=cnt;i++)
        ans=max(ans,dp[n][s[i]]);
    printf("%d\n",ans);
}