KaisuoShutong @ 2018-07-22 15:50:57

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[110][1100],p[1100],con[1100];
long long f[110][1100][1100];
int n,m;
void state()
{
    long long ans=0;
    p[0]=1;
    for(int i=1;i<=p[1];i++) f[1][i][1]=con[a[1][i]];
    for(int i=2;i<=n;i++)
        for(int j=1;j<=p[i];j++)
            for(int k=1;k<=p[i-1];k++)
                if(!(a[i][j]&a[i-1][k]))
                    for(int v=1;v<=p[i-2];v++)
                        if(!(a[i][j]&a[i-2][v])&&!(a[i-1][k]&a[i-2][v]))
                        {
                            f[i][j][k]=max(f[i][j][k],f[i-1][k][v]+con[a[i][j]]);
                            ans=max(ans,f[i][j][k]);
                        }
    printf("%lld\n",ans);
}
int main()
{
    char x;
    scanf("%d %d",&n,&m);
    for(int i=1;i<(1<<m);i++)
        for(int j=0;j<m;j++)
            if((i>>j)&1) con[i]++;
    for(int i=1;i<=n;i++)
    {
        int cn=0,cnt=0;
        for(int j=1;j<=m;j++)
        {
            cin>>x;
            cn=(cn<<1)+(1-(x=='P'));
        }
        for(int j=0;j<(1<<m);j++)
        {
            if((j&(j<<1))||(j&(j<<2))||(j&(j>>1))||(j&(j>>2))||(j&cn)) continue;
            a[i][++p[i]]=j;
        }
    }
    state();
    return 0;
}

by Smile_Cindy @ 2018-07-22 15:52:28

不要开O2再交一次试试

by 览遍千秋 @ 2018-07-22 15:53:27

您MLE了，大概在空间限制的9~10倍这样。

by KaisuoShutong @ 2018-07-22 16:04:30

好，谢谢。 现在WA了

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[110][1100],p[1100],con[1100];
long long f[110][310][310];
int n,m;
void state()
{
    long long ans=0;
    p[0]=1;
    for(int i=1;i<=p[1];i++) f[1][i][1]=con[a[1][i]];
    for(int i=2;i<=n;i++)
        for(int j=1;j<=p[i];j++)
            for(int k=1;k<=p[i-1];k++)
                if(!(a[i][j]&a[i-1][k]))
                    for(int v=1;v<=p[i-2];v++)
                        if(!(a[i][j]&a[i-2][v])&&!(a[i-1][k]&a[i-2][v]))
                        {
                            f[i][j][k]=max(f[i][j][k],f[i-1][k][v]+con[a[i][j]]);
                            ans=max(ans,f[i][j][k]);
                        }
    printf("%lld\n",ans);
}
int main()
{
    char x;
    scanf("%d %d",&n,&m);
    for(int i=1;i<(1<<m);i++)
        for(int j=0;j<m;j++)
            if((i>>j)&1) con[i]++;
    for(int i=1;i<=n;i++)
    {
        int cn=0,cnt=0;
        for(int j=1;j<=m;j++)
        {
            scanf("%c",&x);
            cn=(cn<<1)+(1-(x=='P'));
        }
        for(int j=0;j<(1<<m);j++)
        {
            if((j&(j<<1))||(j&(j<<2))||(j&(j>>1))||(j&(j>>2))||(j&cn)) continue;
            a[i][++p[i]]=j;
        }
    }
    state();
    return 0;
}

by KaisuoShutong @ 2018-07-22 16:06:45

@Alpha 我没开氧气优化

by KaisuoShutong @ 2018-07-24 10:09:42

过了，谢谢各位DALAOOrz...

哇哈哈哈好开森