蒟蒻求助!!!

P2704 [NOI2001] 炮兵阵地

有朋自远方来 @ 2019-07-14 08:38:30

下面代码总是过不了,,,快崩了QAQ

#include<iostream>
#include<cstring>

using namespace std;

int n,m,cnt[1005],s[1005],tot=0,f[105][105][105],a,sg[105],b,ans;
char c;

bool ok(int x,int y)
{
    if(sg[x]&y)  return false;
    return true;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>c;
            if(c=='H')  sg[i]|=(1<<(m-j-1));
        }
    }

    for(int i=0;i<(1<<m);i++)
    {
        if(((i<<1)&i)==0&&((i<<2)&i)==0)  
        {
            a=0;
            s[tot]=i;
            while(i)  i&=(i-1),a++;  
            cnt[tot++]=a;
        }
    }

    memset(f,-1,sizeof(f));
    f[0][0][0]=0;
    for(int j=0;j<tot;j++)
    {
        if(ok(1,s[j]))  f[1][j][0]=cnt[j];
        ans=max(ans,f[1][j][0]);
    }
    for(int i=2;i<=n;i++)
    for(int j=0;j<tot;j++)
        if(ok(i,s[j]))
        for(int k=0;k<tot;k++)
        {
            if(ok(i-1,s[k])&&(s[j]&s[k])==0)
            {
                b=0;
                for(int l=0;l<tot;l++)
                {
                    if(ok(i-2,s[l])&&(s[j]&s[l])==0&&f[i-1][k][l]!=-1)  b=max(b,f[i-1][k][l]);
                }
                f[i][j][k]=max(f[i][j][k],b+cnt[j]);
                if(i==n)  ans=max(ans,f[i][j][k]);
            }
        }

    cout<<ans<<endl;

    return 0;
}

WA (这个样例太水,看不出来啥)


by 有朋自远方来 @ 2019-07-14 09:28:39

结帖


|