zhutier @ 2018-08-27 16:16:47
来自一只超级弱的我
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int n,m,dp[102][1005][1005],obs[103],sit[103],t,answer,g[103];
char a;
int num(int x){
int r=x,ans=0;
while(r>0){
if(r&1) ans++;
r=r>>1;
}
return ans;// printf("the number is%d,it has %d one\n",x,ans);
}
bool jud(int x){
if(x&(x<<1)) return true;
if(x&(x<<2)) return true;
else return false;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a;
if(a=='H') obs[i]+=(1<<(m-j));
}
// printf("obs[%d]=%d\n",i,obs[i]);
}
for(int i=0;i<(1<<m);i++){
if(!jud(i)){
t++;
sit[t]=i;
g[t]=num(i);
if((i&obs[1])==0) dp[1][0][t]=g[t];//printf("dp[1][0][%d]=%d\n",t,dp[1][0][t]);
}
}
for(int i=1;i<=t;i++)
if((sit[i]&obs[1])==0){
for(int j=1;j<=t;j++){
if((sit[j]&obs[2])==0&&(sit[j]&sit[i])==0)
dp[2][i][j]=max(dp[2][i][j],dp[1][0][i]+g[j]);//printf("dp[2][][]=%d\n",dp[2][i][j]);
}
}
for(int i=3;i<=n;i++)
for(int j=1;j<=t;j++)//i
if((sit[j]&obs[i])==0){
for(int k=1;k<=t;k++)//i-1
if((sit[k]&obs[i-1])==0&&(sit[k]&sit[j])==0){
for(int q=1;q<=t;q++){//i-2
if((sit[q]&obs[i-2])==0&&(sit[q]&sit[k])==0){
dp[i][k][j]=max(dp[i][k][j],dp[i-1][q][k]+g[j]);
}
}
}
}
for(int i=1;i<=t;i++)
for(int j=1;j<=t;j++){
answer=max(answer,dp[n][i][j]);
// printf("dp=%d\n",dp[n][i][j]);
}
printf("%d\n",answer);
return 0;
}
by 闻染 @ 2018-08-27 16:23:17
那就吸氧吧,实在不行就抄题解
by zhutier @ 2018-08-27 16:25:36
@sushitong (滑稽)
by goodlearndaydayup @ 2018-08-27 16:27:30
代码过长,不予回复
by zhutier @ 2018-08-27 16:29:04
@违规用户名XRSq*3EK
哭唧唧 其实就三块 初始化第一行 初始化第二行 算接下来的 真的不长的真的不长的
by zhutier @ 2018-08-27 16:39:14
我终于
在抄题解的过程中
找到了bug
给这题过不去的大兄弟一个忠告
三行记得
互相&都要等于0
脑子有点晕忘了
debug四小时
by zhutier @ 2018-08-27 16:40:17
好的 我MLE了 继续解决问题
by _216612 @ 2018-10-19 15:39:33
呵呵