关于#1

Textbook_blasphemy @ 2021-07-11 10:55:58

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m,dp[N][N][N],mp[N],cnt;
struct P{
    int s,num;
}a[N];
char ch;
void pre();
void clean();
int MAX;
int main(){
    clean();
    scanf("%d%d",&n,&m);
    MAX=1<<m;
    getchar();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%c",&ch);
            mp[i]=mp[i]<<1;
            if(ch=='P'){
                mp[i]+=1;
            }else{
                mp[i]+=0;
            }
        }
        getchar();
    }
    pre();
    for(int i=3;i<=n;i++){
        for(int j=1;j<=cnt;j++){
            if((mp[i]&a[j].s)==a[j].s){
                for(int k=1;k<=cnt;k++){
                    if(!(a[j].s&a[k].s)){
                        for(int z=1;z<=cnt;z++){
                            if((!(a[k].s&a[z].s))&&(!(a[j].s&a[z].s))){
                                dp[i][k][j]=max(dp[i][k][j],dp[i-1][z][k]+a[j].num);
                            }
                        }
                    }
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=cnt;i++){
        for(int j=1;j<=cnt;j++){
            ans=max(ans,dp[n][i][j]);
        }
    }
    printf("%d",ans);
    return 0;
}
void pre(){
    for(int i=0;i<MAX;i++){
        if((i&(i<<1))||(i&(i<<2))||(i&(i>>1))||(i&(i>>2))){
            continue;
        }
        cnt++;
        a[cnt].s=i;
        for(int j=0;(1<<j)<=i;j++){
            a[cnt].num+=!!(i&(1<<j));
        }
        if((i&mp[1])==i){
            dp[1][0][cnt]=a[cnt].num;
        }
    }
    for(int i=1;i<=cnt;i++){
        for(int j=1;j<=cnt;j++){
            if((!(a[i].s&a[j].s))&&(mp[2]&a[j].s)==a[j].s){
                dp[2][i][j]=dp[1][0][i]+a[j].num;
            }
        }
    }
}
void clean(){
    memset(a,0,sizeof(a));
    memset(dp,0,sizeof(dp));
    memset(mp,0,sizeof(mp));
    n=m=cnt=0;
}

by fanypcd @ 2021-07-11 10:59:15

@陶（戴）佳伟 本地编译开一下 -std=c++11 再试试

by Textbook_blasphemy @ 2021-07-11 11:02:29

@fanypcd 开了,答案仍是6

by Textbook_blasphemy @ 2021-07-11 11:04:00

问题是在Luogu上答案不对

by __ZXYAKIOI__ @ 2021-07-11 11:11:25

https://www.luogu.com.cn/discuss/show/316981

by fanypcd @ 2021-07-11 11:14:02

@陶（戴）佳伟 读入出问题了

最好不要读 char

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m,dp[N][N][N],mp[N],cnt;
struct P{
    int s,num;
}a[N];
char ch[15];
void pre();
void clean();
int MAX;
int main(){
    clean();
    scanf("%d%d",&n,&m);
    MAX=1<<m;
    getchar();
    for(int i=1;i<=n;i++){
        scanf("%s",ch + 1);
        for(int j=1;j<=m;j++){
            mp[i]=mp[i]<<1;
            if(ch[i]=='P'){
                mp[i]+=1;
            }else{
                mp[i]+=0;
            }
        }
    }
    pre();
    for(int i=3;i<=n;i++){
        for(int j=1;j<=cnt;j++){
            if((mp[i]&a[j].s)==a[j].s){
                for(int k=1;k<=cnt;k++){
                    if(!(a[j].s&a[k].s)){
                        for(int z=1;z<=cnt;z++){
                            if((!(a[k].s&a[z].s))&&(!(a[j].s&a[z].s))){
                                dp[i][k][j]=max(dp[i][k][j],dp[i-1][z][k]+a[j].num);
                            }
                        }
                    }
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=cnt;i++){
        for(int j=1;j<=cnt;j++){
            ans=max(ans,dp[n][i][j]);
        }
    }
    printf("%d",ans);
    return 0;
}
void pre(){
    for(int i=0;i<MAX;i++){
        if((i&(i<<1))||(i&(i<<2))||(i&(i>>1))||(i&(i>>2))){
            continue;
        }
        cnt++;
        a[cnt].s=i;
        for(int j=0;(1<<j)<=i;j++){
            a[cnt].num+=!!(i&(1<<j));
        }
        if((i&mp[1])==i){
            dp[1][0][cnt]=a[cnt].num;
        }
    }
    for(int i=1;i<=cnt;i++){
        for(int j=1;j<=cnt;j++){
            if((!(a[i].s&a[j].s))&&(mp[2]&a[j].s)==a[j].s){
                dp[2][i][j]=dp[1][0][i]+a[j].num;
            }
        }
    }
}
void clean(){
    memset(a,0,sizeof(a));
    memset(dp,0,sizeof(dp));
    memset(mp,0,sizeof(mp));
    n=m=cnt=0;
}

by Textbook_blasphemy @ 2021-07-11 11:17:32

@fanypcd 确实过了#1但是也只过了#1

用cin过了

谢谢!

by fanypcd @ 2021-07-11 11:34:58

@陶（戴）佳伟 因为 ch 数组开小了...