Lalenture @ 2018-08-26 13:18:01
# include <cstdio>
# include <iostream>
# include <cstring>
# include <algorithm>
# include <map>
# define N 120
using namespace std;
int n,m;
char s[N][12];
int f[N];
int dp[N][1101][1101];
int can[1101];
int sum;
int MAX;
int get_sum(int x) //统计情况中1的个数
{
int ans=0;
while(x)
{
if(x & 1) ans++;
x >>= 1;
}
return ans;
}
void prepare()
{
for(int i=0;i<MAX;i++) //预处理比较麻烦,要仔细考虑所有情(我就忘了什么都不放的情况了)
if((i&(i<<2))==0 && (i&(i<<1))==0)
{
can[++sum]=i; //对于cann的处理可以加在单行处理中
if((i&f[1])==0) dp[1][0][i]=get_sum(i);
if((i&f[2])==0) dp[2][0][i]=get_sum(i);
}
for(int i = 1; i <= sum; i++)
for(int j = 1; j <= sum; j++)
if((can[i]&f[1])==0 && (can[j]&f[2])==0 && (can[i]&can[j])==0)
{
dp[2][can[i]][can[j]] = get_sum(can[i]) + get_sum(can[j]);
}
}
int main()
{
ios::sync_with_stdio(false);
freopen("1.in","r",stdin);
cin>>n>>m;
for(int i = 1; i <= n; i++)
scanf("%s",s[i]+1);
MAX = 1 << m;//全局变量在全局定义,不要再次在这里定义,即int MAX,又变成了局部变量
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
if(s[i][j] == 'H') f[i] = (f[i]<<1) + 1;
else f[i] = f[i]<<1;
}
prepare();
for(int i = 3; i <= n; i++)
for(int j = 1; j <= sum; j++)
if((f[i] & can[j]) == 0)
for(int k = 1;k <= sum; k++)
if((f[i-1] & can[k]) == 0 && (can[j] & can[k]) == 0)
for(int l = 1; l <= sum; l++)
if((f[i-2] & can[l]) == 0 && (can[j] & can[l]) == 0 && (can[k] & can[l]) == 0)
{
dp[i][can[k]][can[j]] = max(dp[i][can[k]][can[j]] , dp[i-1][can[l]][can[k]] + get_sum(can[j]));
}
int maxn = 0;
for(int i = 1;i <= sum; i++)
for(int j = 1; j <= sum; j++)
maxn = max(maxn , dp[n][can[i]][can[j]]);
cout<<maxn<<endl;
return 0;
}
这一组数据,用这个代码,直接复制粘贴,答案是6, 将数据储存在一个文件夹里,调用文件夹freopen("1.in","r",stdin)答案就变成7了
by Lalenture @ 2018-08-26 13:33:43
@ACの666 好的 , 谢谢大佬
by Lalenture @ 2018-08-26 14:42:26
@ACの666 我们老师解释了一下,他说用了ios::sync_with_stdio 优化,那么cin cout和scanf printf 不能混用。。