为什么转移时不用考虑前两行的匹配性(状态是否符合地形)?

P2704 [NOI2001] 炮兵阵地

Bluebird_ @ 2022-10-16 06:37:48

求大佬赐教

#include<bits/stdc++.h>
using namespace std;
const int N=101,M=12;
int n,m,a[N],b[(int)1e6],cnt,dp[101][500][500],p[1050];
int ans=0;
void init()
{
    for(int i=0;i<(1<<M);++i)
    {
        if((i<<2)&i)continue;
        if((i<<1)&i)continue;
        b[++cnt]=i;
        int x=i;
        while(x)
        {
            if(x&1)p[cnt]++;
            x>>=1;
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        string s;
        cin>>s;
        for(int j=0;j<s.size();++j)
        {
            if(s[j]=='P')a[i]+=(1<<j);
        }
    }
    init();
    for(int i=1;i<=cnt;++i)
        if((b[i]|a[1])==a[1])
            dp[1][i][1]=p[i],ans=max(ans,p[i]);
    for(int i=2;i<=n;++i)
    {
        for(int j=1;j<=cnt;++j)
        {
            if((b[j]|a[i])!=a[i])continue;
            for(int k=1;k<=cnt;++k)
            {
                //if((b[k]|a[i-1])!=a[i-1])continue;
                if(b[j]&b[k])continue;
                for(int q=1;q<=cnt;++q)
                {
                    //if((b[q]|a[i-2]!=a[i-2]))continue;
                    if(b[j]&b[q])continue;
                    dp[i][j][k]=max(dp[i-1][k][q]+p[j],dp[i][j][k]);
                    ans=max(ans,dp[i][j][k]);
                }
            }       
        }
    }
    cout<<ans<<endl;
    return 0;   
}

在这个地方


    for(int i=2;i<=n;++i)
    {
        for(int j=1;j<=cnt;++j)
        {
            if((b[j]|a[i])!=a[i])continue;//当前行不满足地形要求时跳过
            for(int k=1;k<=cnt;++k)
            {
           //i-1行的状态不满足i-1行地形(若加入这个判断则样例无法通过
                //if((b[k]|a[i-1])!=a[i-1])continue;
                if(b[j]&b[k])continue;
                for(int q=1;q<=cnt;++q)
                {
                //i-2行的状态不满足i-2行地形(若加入这个判断则样例无法通过
                    //if((b[q]|a[i-2]!=a[i-2]))continue;
                    if(b[j]&b[q])continue;
                    dp[i][j][k]=max(dp[i-1][k][q]+p[j],dp[i][j][k]);
                    ans=max(ans,dp[i][j][k]);
                }
            }       
        }

by gyfydkf @ 2022-10-20 09:22:15

如果不符合的话dp数组的值是负无穷的,肯定不会转移,当然有判断肯定更好啊


by Bluebird_ @ 2022-10-29 17:38:09

@gyfydkf 可是我加了判断反而还不能通过样例了...


|