Why WA?

发布时间 2023-05-01 18:39:18作者: ddt_cai

Acwing 292 炮兵阵地

状压dp

#include <bits/stdc++.h>
#define int long long
#define itn int
using namespace std;
int read()
{
    int x=1,a=0;
    char ch=getchar();
    while(ch>'9' || ch<'0')x=(ch=='-')?-1:x,ch=getchar();
    while(ch>='0' && ch<='9')a=(a<<1)+(a<<3)+(ch-'0'),ch=getchar();
    return a*x;
}
vector<int> could;
int n,m;
int mmap[15];
int f[2][1200][1200],cnt[1200];
int lowbit(int x)
{
    return x&(-x);
}
inline int have(int x)
{
    int ret=0;
    while(lowbit(x)!=0)
    {
        ret++;
        x-=lowbit(x);
    }
    return ret;
}
char s[15];
signed main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
    {
        cin>>(s+1);
        for(int j=1;j<=m;j++)
        {
            mmap[i]=(mmap[i]<<1)+(s[j]=='H');
        }
    }
    for(int i=0;i<(1<<m);i++)
    {
        if(!((i&(i>>1))||(i&(i>>2))))
        {
            could.push_back(i);
            cnt[i]=have(i);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(auto now:could)
        {
            if(!(now&mmap[i]))
            for(auto last:could)
            {
                if(!(now&last))
                for(auto last_2:could)
                {
                    if((!(now&last_2))&&(!(last&last_2)))
                    {
                        f[i&1][now][last]=max(f[i&1][now][last],f[(i-1)&1][last][last_2]+cnt[now]);
                    }
                }
            }
        }
    }
    int ans=0;
    for(auto i:could)
    {
        for(auto j:could)
        {
            ans=max(ans,f[n&1][i][j]);
        }
    }
    cout<<ans;
}