yuhui__ @ 2022-02-18 01:45:15
#include<cstdio>
#include<iostream>
using namespace std;
int N=0,M=0;
char C[100][20]={};
int f[120][1200]={},g[120][1200]={};
int cnt[120]={};
int dp[105][100][100]={};
void DFS(int row,int pos,int num,int s)
{
if(pos>=M+1){
f[row][++cnt[row]]=num;
g[row][cnt[row]]=s;
return;
}
DFS(row,pos+1,num,s);
if(C[row][pos]!='H'){
DFS(row,pos+3,num+1,s+(1<<pos));
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>N>>M;
int ans=0;
char x;
for(int i=1;i<=N;++i){
for(int j=1;j<=M;++j){
cin>>x;
C[i][j]=x;
}
DFS(i,1,0,0);
}
for(int i=1;i<=cnt[1];++i){
dp[1][i][0]=f[1][i];
ans=max(ans,dp[1][i][0]);
}
for(int i=2;i<=N;++i){
for(int j=1;j<=cnt[i];++j){
for(int k=1;k<=cnt[i-1];++k){
if(g[i][j]&g[i-1][k]){continue;}
if(i==2){
dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][0]+f[i][j]);
ans=max(ans,dp[i][j][k]);
}
for(int s=1;s<=cnt[i-2];++s){
if(g[i][j]&g[i-2][s]){continue;}
if(g[i-1][k]&g[i-2][s]){continue;}
dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][s]+f[i][j]);
ans=max(ans,dp[i][j][k]);
}
}
}
}
cout<<ans;
return 0;
}
上面方式开O2后RE
下面这种读入方式开O2后MLE
实在看不出问题 求助
for(int i=1;i<=N;++i){
cin>>C[i]+1;
DFS(i,1,0,0);
}
by 寒鸽儿 @ 2022-02-18 05:37:03
@yuhui__
第 5 行C数组开的不够大。
C[110][20] 就过了。