萌新刚学OI，状压dp0分求助

muyang_233 @ 2020-08-10 09:01:43

#include <cstdio>
using namespace std;
int n,m;
int ans;
int res;
int a[105];
int st[1<<10+1];
int cnt[1<<10+1];
char ch[105][15];
int dp[105][75][75];
inline int lowbit(int x){
    return x&(-x);
}
inline int get1(int x){
    int res=0;
    while(x){
        ++res;
        x-=lowbit(x);
    }
    return res;
}
inline void init1(){
    for (int i=0;i<(1<<m);i++){
        if ((!i&(i<<1))&&(!i&(i<<2))&&(!i&(i>>1))&&(!i&(i>>2))){
            st[++res]=i;
            cnt[res]=get1(i);
        }
    }
}
inline void init2(){
    for (int i=1;i<=res;i++){
        if (st[i]|a[1]==a[1]){
            dp[1][i][0]=cnt[i];
        }
    }
    for (int i=1;i<=res;i++){
        for (int j=1;j<=res;j++){
            if ((st[i]|a[2]==a[2])&&(st[j]|a[1]==a[1])&&(st[i]&st[j]==0)){
                dp[2][i][j]=cnt[i]+cnt[j];
            }
        }
    }
}
inline int max(int a,int b){
    return a>b?a:b;
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
        scanf("%s",ch[i]+1);
        for (int j=1;j<=m;j++){
            a[i]=a[i]*2+(ch[i][j]=='P');
        }
    }
    init1();
    init2();
    for (int i=3;i<=n;i++){
        for (int j=1;j<=res;j++){
            if (st[j]|a[i]!=a[i]){
                continue;
            }
            for (int k=1;k<=res;k++){
                if ((st[k]|a[i-1]!=a[i-1])||(st[j]&st[k])){
                    continue;
                }
                for (int l=1;l<=res;l++){
                    if ((st[l]|a[i-2]!=a[i-2])||(st[j]&st[l])||(st[k]&st[l])){
                        continue;
                    }
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][l]+cnt[j]);
                }
            }
        }
    }
    for (int i=1;i<=res;i++){
        printf("%d %d\n",st[i],cnt[i]);
    }
    for (int i=1;i<=res;i++){
        for (int j=1;j<=res;j++){
            ans=max(ans,dp[n][i][j]);
        }
    }
    printf("%d",ans);
    return 0;
}

by 190040257a @ 2020-08-18 19:45:08

@muyang_233 大佬您好，我没仔细看您的代码，我觉得问题应该是第一第二行没有提前处理（随便看了看想的，我自己还在调试，错了勿喷）

by muyang_233 @ 2020-08-19 08:19:05

@190040257a 有的呀，init2()

by 190040257a @ 2020-08-19 08:44:40

@muyang_233 也有可能是括号加少了（|&）优先级问题,我在您代码中的几行|&判断中多加了括号，就可以输出了（但答案还是错的）

by 190040257a @ 2020-08-19 08:48:50

@muyang_233 确实是括号加少了

#include <cstdio>
using namespace std;
int n,m;
int ans;
int res;
int a[105];
int st[1<<10+1];
int cnt[1<<10+1];
char ch[105][15];
int dp[105][75][75];
inline int lowbit(int x){
    return x&(-x);
}
inline int get1(int x){
    int res=0;
    while(x){
        ++res;
        x-=lowbit(x);
    }
    return res;
}
inline void init1(){
    for (int i=0;i<(1<<m);i++){
        if ((!(i&(i<<1)))&&(!(i&(i<<2)))&&(!(i&(i>>1)))&&(!(i&(i>>2)))){
            st[++res]=i;
            cnt[res]=get1(i);
        }
    }
}
inline void init2(){
    for (int i=1;i<=res;i++){
        if (st[i]|a[1]==a[1]){
            dp[1][i][0]=cnt[i];
        }
    }
    for (int i=1;i<=res;i++){
        for (int j=1;j<=res;j++){
            if (((st[i]|a[2])==a[2])&&((st[j]|a[1])==a[1])&&((st[i]&st[j])==0)){
                dp[2][i][j]=cnt[i]+cnt[j];
            }
        }
    }
}
inline int max(int a,int b){
    return a>b?a:b;
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
        scanf("%s",ch[i]+1);
        for (int j=1;j<=m;j++){
            a[i]=a[i]*2+(ch[i][j]=='P');
        }
    }
    init1();
    init2();
    for (int i=3;i<=n;i++){
        for (int j=1;j<=res;j++){
            if ((st[j]|a[i])!=a[i]){
                continue;
            }
            for (int k=1;k<=res;k++){
                if (((st[k]|a[i-1])!=a[i-1])||(st[j]&st[k])){
                    continue;
                }
                for (int l=1;l<=res;l++){
                    if (((st[l]|a[i-2])!=a[i-2])||(st[j]&st[l])||(st[k]&st[l])){
                        continue;
                    }
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][l]+cnt[j]);
                }
            }
        }
    }

    for (int i=1;i<=res;i++){
        for (int j=1;j<=res;j++){
            ans=max(ans,dp[n][i][j]);
        }
    }
    printf("%d",ans);
    return 0;
}

https://www.luogu.com.cn/record/37264284 加几个括号就能A了

by muyang_233 @ 2020-08-19 09:04:31

@190040257a 过了，谢谢巨佬，以后会注意的

by muyang_233 @ 2020-08-19 09:04:57

此贴完结