50分求助

Scherzo @ 2022-11-22 09:14:22

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=110;
const int W=N<<2;

int n,m,cnt;
int num[W],s[W],g[N][N];
int f[N][W][W],ans;

inline void dp () {
    for (register int i=1;i<=cnt;i++) {
        if ((s[i]|g[1][0])!=g[1][0]) continue;
        f[1][1][i]=num[i];
        for (register int j=1;j<=cnt;j++) {
            if ((s[j]|g[2][0])!=g[2][0]) continue;
            if ((s[i]&s[j])) continue;
            f[2][i][j]=num[i]+num[j];
        }
    }
    //row
    for (register int i=3;i<=n;i++) {
        for (register int j=1;j<=cnt;j++) {
            for (register int k=1;k<=cnt;k++) {
                for (register int t=1;t<=cnt;t++) {
                    if ((s[j]|g[i-2][0])!=g[i-2][0]) continue;
                    if ((s[k]|g[i-1][0])!=g[i-1][0]) continue;
                    if ((s[t]|g[i][0])!=g[i][0]) continue;
                    //-2 & -1
                    if ((s[j]&s[k])) continue;
                    //-1 & this
                    if ((s[k]&s[t])) continue;
                    //-2 & this
                    if ((s[j]&s[t])) continue;

                    f[i][k][t]=f[i-1][j][k]+num[t];
                }
            }
        }
    }
}

int main () {
    scanf("%d%d",&n,&m);
    for (register int i=1;i<=n;i++) {
        for (register int j=1;j<=m;j++) {
            char c; cin>>c;
            if (c=='P') g[i][j]=1;
            else g[i][j]=0;
            g[i][0]+=pow(2,m-j)*g[i][j];
        }
    }
    for (register int i=0;i<(1<<m);i++) {
        if (i&(i<<1)|(i&(i<<2))) continue;
        int sum=0;
        for (register int j=0;j<m;j++) {
            if (i&(1<<j)) sum++;
        }
        s[++cnt]=i;
        num[cnt]=sum; 
    }
    dp();
    for (register int i=1;i<=cnt;i++) {
        for (register int j=1;j<=cnt;j++) {
            ans=max(ans,f[n][i][j]);
        }
    }
    printf("%d\n",ans);
    return 0;
}

by FstAutoMaton @ 2022-12-14 19:00:04

给你看看我的吧

#include <bits/stdc++.h>
using namespace std;
int n, m, cnt, sum[105], dp[105][105][105], mp[105], op[105];
char a;
int getsum( int x )
{
    int num = 0;
    while( x )
    {
        if( x & 1 ) num ++;
        x >>= 1;
    }
    return num;
}
bool check( int x )
{
    if( x & ( x >> 1 ) ) return 1;
    if( x & ( x >> 2 ) ) return 1;
    if( x & ( x << 1 ) ) return 1;
    if( x & ( x << 2 ) ) return 1;
    return 0;
}
int main()
{
    cin >> n >> m;
    int N = ( 1 << m ) - 1;
    for( int i = 1; i <= n; i ++ )
    {
        for( int j = 1; j <= m; j ++ )
        {
            cin >> a;
            mp[i] = ( mp[i] << 1 ) + ( a == 'H' );
        }
    }
    for( int i = 0; i <= N; i ++ )
    {
        if( check( i ) ) continue;
        op[++ cnt] = i;
        sum[cnt] = getsum( i );
        if( !( i & mp[1] ) ) 
        {
            dp[1][cnt][0] = sum[cnt];
        }
    }
    for( int i = 1; i <= cnt; i ++ )
    {
        for( int j = 1; j <= cnt; j ++ )
        {
            if( op[i] & op[j] ) continue;
            if( ( op[i] & mp[2] ) ) continue;
            dp[2][i][j] = dp[1][j][0] + sum[i];
        }
    }
    for( int i = 3; i <= n; i ++ )
    {
        for( int j = 1; j <= cnt; j ++ ) //本行
        {
            if( ( op[j] & mp[i] ) ) continue;
            for( int k = 1; k <= cnt; k ++ ) //上行
            {
                if( ( op[k] & mp[i - 1] ) ) continue;
                if( op[j] & op[k] ) continue;
                for( int l = 1; l <= cnt; l ++ ) //上上行
                {
                    if( ( op[l] & mp[i - 2] ) ) continue;
                    if( ( op[j] & op[l] ) || ( op[k] & op[l] ) ) continue;
                    dp[i][j][k] = max( dp[i - 1][k][l] + sum[j], dp[i][j][k] );
                }
            }
        }
    }
    int ans = 0;
    // for( int i = 1; i <= n; i ++ )
    // {
    //  cout << dp[1][i][0] << " ";
    // }
    for( int i = 1; i <= cnt; i ++ )
    {
        for( int j = 0; j <= cnt; j ++ )
        {
            ans = max( ans, dp[n][i][j] );
        }
    }
    cout << ans;
}

by FstAutoMaton @ 2022-12-14 19:00:31

@Scherzo

by Scherzo @ 2022-12-14 21:37:52

@caoshurui 谢啦 已经AC了