凑_友希那 @ 2018-09-05 12:46:57
洛谷IDE上也是7
但本机是6
#include <bits/stdc++.h>
int dp[101][101][101];
int cnt, t[101];
int sta[101], sum[101];
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < m; j++) {
char ch = getchar();
while (ch == ' ' || ch == '\n') ch = getchar();
if (ch == 'H') t[i] = t[i] | (1 << j);
}
}//处理有山的位置
for (int i = 0; i < (1 << m); i++) {
if ((i & (i << 1)) || (i & (i << 2)) || (i & (i >> 1)) || (i & (i >> 2))) continue;
sta[++cnt] = i;
for (int k = 0; k < m; k++) {
if (i & (1 << k)) sum[cnt]++;
}
if (i & t[1]) continue;
else dp[1][0][cnt] = sum[cnt];//初始化
//处理可用状态
}
for (int i = 1; i <= cnt; i++) {
for (int j = 1; j <= cnt; j++) {
if (sta[i] & sta[j] || sta[j] & t[2]) continue;
dp[2][i][j] = std::max(dp[2][i][j], dp[1][0][i] + sum[j]);
}
}//处理第二行
for (int i = 3; i <= n; i++) {
for (int j = 1; j <= cnt; j++) {
if (sta[j] & t[i]) continue;
for (int k = 1; k <= cnt; k++) {
if (sta[j] & sta[k]) continue;
for (int l = 1; l <= cnt; l++) {
if (sta[k] & sta[l] || sta[j] & sta[l]) continue;
dp[i][k][j] = std::max(dp[i][k][j], dp[i - 1][l][k] + sum[j]);//DP
}
}
}
}
int ans = 0;
for (int i = 1; i <= cnt; i++) {
for (int j = 1; j <= cnt; j++) ans = std::max(ans, dp[n][i][j]);//处理最大值
}
printf("%d\n", ans);
return 0;
}
by heyongxin @ 2018-09-05 12:52:58
....
by 青梧 @ 2018-09-05 17:40:46
@ILLF_mTx
可能是换行符的问题
在在线IDE中把
PHPP
PPHH
PPPP
PHPP
把
while (ch!='P'&&ch!='H') ch=getchar();
就能过了
by 凑_友希那 @ 2018-09-06 12:37:18
@GTX_TITAN 谢大佬