状压 DP WA 求助！

OldDriverTree @ 2023-04-30 15:11:56

#include<bits/stdc++.h>
using namespace std;
const int N=100,M=1024;
int n,m,ans,g[N],cnt[M];
int f[2][M][M]; vector<int> S;

char gc() {
    char ch=0; while (!isalpha(ch) )
    ch=getchar(); return ch;
}
bool check(int x) {
    return !(x&x>>1||x&x>>2);
}
int count(int x) {
    int cnt=0; while (x)
    cnt++,x&=(x-1); return cnt;
}
int mian()
{
    scanf("%d%d",&n,&m);
    for (int i=0;i<n;i++) for (int j=0;j<n;j++) g[i]|=(gc()^'P')<<j;
    for (int i=0;i<1<<m;i++) if (check(i) ) S.push_back(i),cnt[i]=count(i);

    for (int i=0;i<n;i++)
        for (int x:S) for (int y:S) for (int z:S)
            if ( !(x&y) && !(x&z) && !(y&z) && !(g[i]&x) )
                f[i&1][x][y]=max(f[i&1][x][y],f[i-1&1][y][z]+cnt[x]);
    for (int u:S) for (int v:S) if (!(u&v) ) ans=max(ans,f[n-1&1][u][v]);
    printf("%d",ans); return 0;
}

by ForgotDream_CHN @ 2023-04-30 17:24:24

@guoxiangyu66 int mian？？？？

by OldDriverTree @ 2023-04-30 17:26:36

@ForgotDream_CHN 额，代码复制错了，应该是 int main （

by ForgotDream_CHN @ 2023-04-30 17:26:38

改了之后虽然没 WA，但是 T 了一大堆

by OldDriverTree @ 2023-04-30 17:27:25

@ForgotDream_CHN 哪错了？

by ForgotDream_CHN @ 2023-04-30 17:33:47

@guoxiangyu66 for (int i=0;i<n;i++) for (int j=0;j<n;j++) 应该是 for (int i=0;i<n;i++) for (int j=0;j<m;j++) 吧

by ForgotDream_CHN @ 2023-04-30 17:34:36

改了之后 WA 一堆

by ForgotDream_CHN @ 2023-04-30 17:43:42

@guoxiangyu66

#include<bits/stdc++.h>
using namespace std;
const int N=100,M=1024;
int n,m,ans,g[N],cnt[M];
int f[2][M][M]; vector<int> S;

char gc() {
    char ch=0; 
        while (!isalpha(ch) )
        ch=getchar(); 
        return ch;
}
bool check(int x) {
    return !(x&x>>1||x&x>>2);
}
int count(int x) {
    int cnt=0; 
        while (x)
        cnt++,x&=(x-1); 
        return cnt;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=0;i<n;i++) for (int j=0;j<m;j++) {
            g[i] = (g[i] << 1) + (gc() == 'H');
        }
    for (int i=0;i<1<<m;i++) if (check(i) ) S.push_back(i),cnt[i]=count(i);

    for (int i=0;i<n;i++)
        for (int x:S) for (int y:S) for (int z:S)
            if ( !(x&y) && !(x&z) && !(y&z) && !(g[i]&x) )
                f[i&1][x][y]=max(f[i&1][x][y],f[(i-1)&1][y][z]+cnt[x]);
    for (int u:S) for (int v:S) if (!(u&v) ) ans=max(ans,f[(n-1)&1][u][v]);
    printf("%d",ans); return 0;
}

改好了

by ForgotDream_CHN @ 2023-04-30 17:44:30

大致错误就是读入的时候出了问题，gc()^'P' 他不是个 01 值

by OldDriverTree @ 2023-04-30 17:52:22

@ForgotDream_CHN thx，通过了，已关，此帖结