萌新初学状压dp，结果样例都没过（(⊙o⊙)…）

STUDENT00 @ 2022-09-27 20:47:05

#include<bits/stdc++.h>
using namespace std;
int n,m,a[101],p,dp[101][101][101],ans;
char c[101][11];
void work(){
    for(int i=1;i<(1<<n);i++){
        if((i&(i<<1))||(i&(i<<2))) continue;
        p++;
        a[p]=i;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s",c[i]+1);
    work();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=p;j++){
            int s=0,t=a[j];
            while(t){
                t&=(t-1);
                s++;
            }
            for(int z=1;z<=p;z++){
                if(a[j]&a[z]) continue;
                int maxs=0;
                for(int k=1;k<=p;k++){
                    if((a[j]&a[k])||(a[z]&a[k])) continue;
                    maxs=max(maxs,dp[i][z][k]);
                }
                dp[i][j][z]=maxs+s;
            }
        }
    }
    for(int i=1;i<=p;i++){
        for(int j=1;j<=p;j++) ans=max(ans,dp[n][i][j]);
    }
    printf("%d",ans);
    return 0;
}

by STUDENT00 @ 2022-09-27 20:49:19

改了一个地方，结果样例输出变成5

#include<bits/stdc++.h>
using namespace std;
int n,m,a[101],p,dp[101][101][101],ans;
char c[101][11];
void work(){
    for(int i=0;i<(1<<m);i++){
        if((i&(i<<1))||(i&(i<<2))) continue;
        p++;
        a[p]=i;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s",c[i]+1);
    work();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=p;j++){
            int s=0,t=a[j];
            while(t){
                t&=(t-1);
                s++;
            }
            for(int z=1;z<=p;z++){
                if(a[j]&a[z]) continue;
                int maxs=0;
                for(int k=1;k<=p;k++){
                    if((a[j]&a[k])||(a[z]&a[k])) continue;
                    maxs=max(maxs,dp[i][z][k]);
                }
                dp[i][j][z]=maxs+s;
            }
        }
    }
    for(int i=1;i<=p;i++){
        for(int j=1;j<=p;j++) ans=max(ans,dp[n][i][j]);
    }
    printf("%d",ans);
    return 0;
}

by 淸梣ling @ 2022-09-27 20:54:42

@YuRuochen 你的 c 数组没有用到（忘记用了吧

by STUDENT00 @ 2022-09-27 20:55:05

ooo

by STUDENT00 @ 2022-09-27 21:19:12

@淸梣ling dalao，为什么现在变成0分了呢？

#include<bits/stdc++.h>
using namespace std;
int n,m,a[101][101],dp[101][101][101],ans;
char c[101][11];
void work(){
    for(int k=1;k<=n;k++){
        for(int i=0;i<(1<<m);i++){
            if((i&(i<<1))||(i&(i<<2))) continue;
            for(int j=1;j<=n;j++){
                if(c[k][j]=='H'&&((i>>(j-1))&1)) continue;
            }
            a[k][++a[k][0]]=i;
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s",c[i]+1);
    work();
    for(int i=2;i<=n;i++){
        for(int j=1;j<=a[i][0];j++){
            int s=0,t=a[i][j];
            while(t){
                t&=(t-1);
                s++;
            }
            for(int z=1;z<=a[i+1][0];z++){
                if(a[i][j]&a[i+1][z]) continue;
                int maxs=0;
                for(int k=1;k<=a[i+2][0];k++){
                    if((a[i][j]&a[i+2][k])||(a[i+1][z]&a[i+2][k])) continue;
                    maxs=max(maxs,dp[i][z][k]);
                }
                dp[i][j][z]=maxs+s;
            }
        }
    }
    for(int i=1;i<=a[n][0];i++){
        for(int j=1;j<=a[n][0];j++) ans=max(ans,dp[n][i][j]);
    }
    printf("%d",ans);
    return 0;
}

by STUDENT00 @ 2022-09-27 21:19:39

说错了，是输出0

by STUDENT00 @ 2022-09-27 21:23:06

@淸梣ling dalao，现在20，萌新不知道怎么改，还恳请大佬帮忙（可以吗？）

#include<bits/stdc++.h>
using namespace std;
int n,m,a[103][101],dp[101][101][101],ans;
char c[101][11];
void work(){
    for(int k=1;k<=n+2;k++){
        for(int i=0;i<(1<<m);i++){
            if((i&(i<<1))||(i&(i<<2))) continue;
            for(int j=1;j<=n;j++){
                if(c[k][j]=='H'&&((i>>(j-1))&1)) continue;
            }
            a[k][++a[k][0]]=i;
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s",c[i]+1);
    work();
    for(int i=2;i<=n;i++){
        for(int j=1;j<=a[i][0];j++){
            int s=0,t=a[i][j];
            while(t){
                t&=(t-1);
                s++;
            }
            for(int z=1;z<=a[i+1][0];z++){
                if(a[i][j]&a[i+1][z]) continue;
                int maxs=0;
                for(int k=1;k<=a[i+2][0];k++){
                    if((a[i][j]&a[i+2][k])||(a[i+1][z]&a[i+2][k])) continue;
                    maxs=max(maxs,dp[i-1][z][k]);
                }
                dp[i][j][z]=maxs+s;
            }
        }
    }
    for(int i=1;i<=a[n][0];i++){
        for(int j=1;j<=a[n][0];j++) ans=max(ans,dp[n][i][j]);
    }
    printf("%d",ans);
    return 0;
}

by 淸梣ling @ 2022-09-27 21:23:52

@YuRuochen line10 你 continue 在 j 的 for 里面啊，直接这样是错的。

先 break 再 continue

by STUDENT00 @ 2022-09-27 21:30:30

@淸梣ling dalao，为什么现在样例输出4了？

#include<bits/stdc++.h>
using namespace std;
int n,m,a[103][101],dp[101][101][101],ans;
char c[101][11];
void work(){
    for(int k=1;k<=n+2;k++){
        for(int i=0;i<(1<<m);i++){
            if((i&(i<<1))||(i&(i<<2))) continue;
            bool flag=0;
            for(int j=1;j<=n;j++){
                if(c[k][j]=='H'&&((i>>(j-1))&1)){
                    flag=1;
                    break;
                }
            }
            if(flag) continue;
            a[k][++a[k][0]]=i;
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s",c[i]+1);
    work();
    for(int i=2;i<=n;i++){
        for(int j=1;j<=a[i][0];j++){
            int s=0,t=a[i][j];
            while(t){
                t&=(t-1);
                s++;
            }
            for(int z=1;z<=a[i+1][0];z++){
                if(a[i][j]&a[i+1][z]) continue;
                int maxs=0;
                for(int k=1;k<=a[i+2][0];k++){
                    if((a[i][j]&a[i+2][k])||(a[i+1][z]&a[i+2][k])) continue;
                    maxs=max(maxs,dp[i-1][z][k]);
                }
                dp[i][j][z]=maxs+s;
            }
        }
    }
    for(int i=1;i<=a[n][0];i++){
        for(int j=1;j<=a[n][0];j++) ans=max(ans,dp[n][i][j]);
    }
    printf("%d",ans);
    return 0;
}

by STUDENT00 @ 2022-09-27 21:34:00

@淸梣ling dalao，我做了一些微调，可是为什么样例竟然输出2了？！（越来越离谱）

#include<bits/stdc++.h>
using namespace std;
int n,m,a[103][101],dp[101][101][101],ans;
char c[101][11];
void work(){
    for(int k=1;k<=n+2;k++){
        for(int i=0;i<(1<<m);i++){
            if((i&(i<<1))||(i&(i<<2))) continue;
            bool flag=0;
            for(int j=1;j<=n;j++){
                if(c[k][j]=='H'&&((i>>(j-1))&1)){
                    flag=1;
                    break;
                }
            }
            if(flag) continue;
            a[k][++a[k][0]]=i;
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s",c[i]+1);
    work();
    for(int i=n;i>=1;i--){
        for(int j=1;j<=a[i][0];j++){
            int s=0,t=a[i][j];
            while(t){
                t&=(t-1);
                s++;
            }
            for(int z=1;z<=a[i+1][0];z++){
                if(a[i][j]&a[i+1][z]) continue;
                int maxs=0;
                for(int k=1;k<=a[i+2][0];k++){
                    if((a[i][j]&a[i+2][k])||(a[i+1][z]&a[i+2][k])) continue;
                    maxs=max(maxs,dp[i-1][z][k]);
                }
                dp[i][j][z]=maxs+s;
            }
        }
    }
    for(int i=1;i<=a[1][0];i++){
        for(int j=1;j<=a[1][0];j++) ans=max(ans,dp[1][i][j]);
    }
    printf("%d",ans);
    return 0;
}

by STUDENT00 @ 2022-09-27 21:37:11

终于过样例了！可惜变成了30分

#include<bits/stdc++.h>
using namespace std;
int n,m,a[103][101],dp[101][101][101],ans;
char c[101][11];
void work(){
    for(int k=1;k<=n+2;k++){
        for(int i=0;i<(1<<m);i++){
            if((i&(i<<1))||(i&(i<<2))) continue;
            bool flag=0;
            for(int j=1;j<=n;j++){
                if(c[k][j]=='H'&&((i>>(j-1))&1)){
                    flag=1;
                    break;
                }
            }
            if(flag) continue;
            a[k][++a[k][0]]=i;
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s",c[i]+1);
    work();
    for(int i=n;i>=1;i--){
        for(int j=1;j<=a[i][0];j++){
            int s=0,t=a[i][j];
            while(t){
                t&=(t-1);
                s++;
            }
            for(int z=1;z<=a[i+1][0];z++){
                if(a[i][j]&a[i+1][z]) continue;
                int maxs=0;
                for(int k=1;k<=a[i+2][0];k++){
                    if((a[i][j]&a[i+2][k])||(a[i+1][z]&a[i+2][k])) continue;
                    maxs=max(maxs,dp[i+1][z][k]);
                }
                dp[i][j][z]=maxs+s;
            }
        }
    }
    for(int i=1;i<=a[1][0];i++){
        for(int j=1;j<=a[2][0];j++) ans=max(ans,dp[1][i][j]);
    }
    printf("%d",ans);
    return 0;
}