跪求大佬帮忙

P2704 [NOI2001] 炮兵阵地

jzy_go @ 2020-08-23 10:03:52

蒟蒻刚学c++一分钟,求助大佬,实在不会了(哭

#include<bits/stdc++.h>
using namespace std;
inline long long read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+(ch-'0');
        ch=getchar();
    }
    return x*f;
}
int n,m;
struct node{
    int num;
    int a[1001];
}a[1001];
int w[1001][1001];
int f[1001][1001];
void chuli(int x,int y)
{
    for(int j=0;j<(1<<m);j++)
    {
        if((j&(j<<1))||(j&(j>>1))||(j&y)||(j&(j<<2))||(j&(j>>2)))
        continue;
        a[x].num++;
        a[x].a[a[x].num]=j;
    }
}
int main()
{
    n=read();
    m=read();
    int x;
    char ch;
    for(int i=1;i<=n;i++)
    {
        int y=0;
        for(int j=1;j<=m;j++)
        {
            ch=getchar();
            if(ch=='H')
            x=0;
            else
            x=1;
            y=y*2+1-x;
        }
        chuli(i,y);
        ch=getchar();
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=a[i].num;j++)
        {
            int kk=a[i].a[j];
            while(kk)
            {
                if(kk&1)
                w[i][j]++;
                kk=kk>>1;
            }
        }
    }
    for(int j=1;j<=a[2].num;j++)
    {
        for(int k=1;k<=a[1].num;k++)
        {
            if(a[2].a[j]&a[1].a[k])
            continue;
            f[2][j]=max(f[2][j],f[1][k]+w[2][j]);
        }
    }
    for(int i=3;i<=n;i++)
    {
        for(int j=1;j<=a[i].num;j++)
        {
            for(int k=1;k<=a[i-1].num;k++)
            if(a[i].a[j]&a[i-1].a[k])
                continue;
            else
            for(int o=1;o<=a[i-2].num;o++)
            {
                if((a[i].a[j]&a[i-2].a[o])||(a[i-1].a[k]&a[i-2].a[o]))
                continue;
                f[i][j]=max(f[i][j],f[i-1][k]+f[i-2][o]+w[i][j]);
            }
        }
    }
    int ans=0;
    for(int j=1;j<=a[n].num;j++)
    {
        ans=max(ans,f[n][j]);
    }
    cout<<ans<<endl;
    return 0;
}

|