hhdddkk @ 2020-07-24 21:19:57

#include<bits/stdc++.h>
using namespace std;
int m,n;
int dp[3][(1<<10)][(1<<10)];
char mp[101][11];
int ans;
bool vis[3][(1<<10)][(1<<10)],v[1<<10];
inline bool Check(int l,int st,int pre){
    if(st&pre) return false;
    for(int i=0;i<m;i++){   
        if(st&(1<<i)){
            if(mp[l][i+1]=='H') return false;
        }
        if(pre&(1<<i)){
            if(mp[l-1][i+1]=='H') return false;
        }
    }
    vis[l%2][st][pre]=1;
    int t=st;
    while(t){
        dp[l%2][st][pre]++;
        t=t-(t&-t);
    }
    if(l==2){
        int cnt=0;
        int t=pre;
        while(t){
            cnt++;
            t=t-(t&-t);
        }
        dp[0][st][pre]+=cnt;
    }
    return true;
}
inline bool judge(int now,int pre){
    if(now&pre) return false;
    return true;
}
void solve(){
    if(n==1){
        for(int i=1;i<=m;){
            if(mp[1][i]=='H'){
                i++;
                continue;
            }
            ans++;
            i+=3;
        }
    }

    for(register int i=2;i<=n;i++)
        for(register int j=0;j<=(1<<m)-1;j++){
            if(v[j]) continue;
            for(register int k=0;k<=(1<<m)-1;k++){
                if(v[k]) continue;
                dp[i%2][j][k]=0;
                vis[i%2][j][k]=0;
                if(!Check(i,j,k)) continue;
                int cnt=dp[i%2][j][k];
                dp[i%2][j][k]=0;
                for(register int l=0;l<=(1<<m)-1;l++)
                   if(vis[i%2][j][k]&&vis[(i-1)%2][k][l]&&judge(j,l))
                       dp[i%2][j][k]=max(dp[i%2][j][k],dp[(i-1)%2][k][l]);
                dp[i%2][j][k]+=cnt; 
                ans=max(ans,dp[i%2][j][k]);
            }
        }
    printf("%d",ans);           
    return;
}
int main(){
    scanf("%d%d",&n,&m);
    getchar();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            mp[i][j]=getchar();
        getchar();
    }
    for(int i=1;i<(1<<m);i++){
        for(int j=0;j<m;j++){
            if((i&(1<<j))&&j&&(i&(1<<(j-1)))) v[i]=1;
            if((i&(1<<j))&&j>=2&&(i&(1<<(j-2)))) v[i]=1;
        }
    }
    solve();
    return 0;
}

by PersistentLife @ 2020-07-24 21:57:20

谔谔

by PersistentLife @ 2020-07-24 21:57:46

一日三题没烦恼，就选老师秘制现场捉虫服务（（（

by Demoe @ 2020-07-24 22:00:42

改了读入

#include<bits/stdc++.h>
using namespace std;
int m,n;
int dp[3][(1<<10)][(1<<10)];
char mp[101][11];
int ans;
bool vis[3][(1<<10)][(1<<10)],v[1<<10];
inline bool Check(int l,int st,int pre){
    if(st&pre) return false;
    for(int i=0;i<m;i++){   
        if(st&(1<<i)){
            if(mp[l][i+1]=='H') return false;
        }
        if(pre&(1<<i)){
            if(mp[l-1][i+1]=='H') return false;
        }
    }
    vis[l%2][st][pre]=1;
    int t=st;
    while(t){
        dp[l%2][st][pre]++;
        t=t-(t&-t);
    }
    if(l==2){
        int cnt=0;
        int t=pre;
        while(t){
            cnt++;
            t=t-(t&-t);
        }
        dp[0][st][pre]+=cnt;
    }
    return true;
}
inline bool judge(int now,int pre){
    if(now&pre) return false;
    return true;
}
void solve(){
    if(n==1){
        for(int i=1;i<=m;){
            if(mp[1][i]=='H'){
                i++;
                continue;
            }
            ans++;
            i+=3;
        }
    }

    for(register int i=2;i<=n;i++)
        for(register int j=0;j<=(1<<m)-1;j++){
            if(v[j]) continue;
            for(register int k=0;k<=(1<<m)-1;k++){
                if(v[k]) continue;
                dp[i%2][j][k]=0;
                vis[i%2][j][k]=0;
                if(!Check(i,j,k)) continue;
                int cnt=dp[i%2][j][k];
                dp[i%2][j][k]=0;
                for(register int l=0;l<=(1<<m)-1;l++)
                   if(vis[i%2][j][k]&&vis[(i-1)%2][k][l]&&judge(j,l))
                       dp[i%2][j][k]=max(dp[i%2][j][k],dp[(i-1)%2][k][l]);
                dp[i%2][j][k]+=cnt; 
                ans=max(ans,dp[i%2][j][k]);
            }
        }
    printf("%d",ans);           
    return;
}
int main(){
    scanf("%d%d",&n,&m);
    getchar();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            cin>>mp[i][j];
    }
    for(int i=1;i<(1<<m);i++){
        for(int j=0;j<m;j++){
            if((i&(1<<j))&&j&&(i&(1<<(j-1)))) v[i]=1;
            if((i&(1<<j))&&j>=2&&(i&(1<<(j-2)))) v[i]=1;
        }
    }
    solve();
    return 0;
}

by hhdddkk @ 2020-07-24 22:13:27

@Daniel_Jiang 应该是行末有空格导致getchar会读入错误，谢谢大佬

by 地球协和联盟 @ 2020-07-26 21:47:43

@hhdddkk 这题难度有问题...

明明普及/提高-的题

by 地球协和联盟 @ 2020-07-26 21:48:28

@hhdddkk 我也卡在读入上面了...

by Mr_H2T @ 2021-02-21 17:59:35

貌似其他点行末都是LF，#1行末是CR LF导致getchar出问题