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 Gypsophila @ 2018-08-26 13:21:14
@Lalenture dp[120][1101][1101],这么大的数组开不下
by Lalenture @ 2018-08-26 13:23:19
@ACの666 但是这个数据很小啊,你把数组变小了还是那样的
by Lalenture @ 2018-08-26 13:23:47
@ACの666 数组 可以开的 没爆MLE
by Gypsophila @ 2018-08-26 13:24:15
@Lalenture 数组太大会有离奇问题
by Lalenture @ 2018-08-26 13:25:19
@ACの666 我把那个数组变成 dp[50][100][100]还是那样的。。
by Lalenture @ 2018-08-26 13:25:51
@ACの666 数据发给你,你可以去测你一下 5 4 PHPP PPHH PPPP PHPP PHHP
by Lalenture @ 2018-08-26 13:26:05
@ACの666 5 4
PHPP
PPHH
PPPP
PHPP
PHHP
by Gypsophila @ 2018-08-26 13:28:45
@Lalenture 我这里一测发生了玄学事件
系统提示:
terminate called after throwing an instance of 'std::ios_base::failure'
what(): basic_filebuf::underflow error reading the file
This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.
by Lalenture @ 2018-08-26 13:30:02
@ACの666 什么意思? 我英语不好啊,大佬-,-
by Gypsophila @ 2018-08-26 13:31:38
@Lalenture 我也不知道。。第一次发生这种错误。。
话说这题只用保存有用的60个状态就行了,不用开到1024