第一个测试点WA了,下载下来看第一个测试点就是样例,但是不管是在本地还是洛谷IDE,运行我的代码得到的答案都是6,提交就是错的,一会儿是7一会儿是5,求救求救求救!!!
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int read()
{
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return x * f;
}
const int NUM = 100;
int n, m;
int eachOne[1 << 10];
int Maps[NUM + 5];
int dp[1 << 10][1 << 10][4];
inline int getOne(int x)
{
int res = 0;
while (x)
{
if (x & 1)
res++;
x >>= 1;
}
return res;
}
int main()
{
n = read(), m = read();
for (int i = 0; i < (1 << m); ++i)
eachOne[i] = getOne(i);
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
Maps[i] <<= 1;
Maps[i] += (getchar() == 'P' ? 0 : 1);
}
getchar();
}
for (int now = 0; now < (1 << m); ++now)
if ((now & Maps[0]) == 0 && (now & (now << 1)) == 0 && (now & (now << 2)) == 0)
dp[0][now][0] = eachOne[now];
for (int lastLine = 0; lastLine < (1 << m); ++lastLine)
for (int now = 0; now < (1 << m); ++now)
if ((now & lastLine) == 0 && (now & Maps[1]) == 0 && (lastLine & Maps[0]) == 0 && (now & (now << 1)) == 0 && (now & (now << 2)) == 0 && (lastLine & (lastLine << 1)) == 0 && (lastLine & (lastLine << 2)) == 0)
dp[lastLine][now][1] = eachOne[lastLine] + eachOne[now];
for (int i = 2; i < n; ++i)
for (int lastLine = 0; lastLine < (1 << m); ++lastLine)
if ((lastLine & (lastLine << 1)) == 0 && (lastLine & (lastLine << 2)) == 0 && (lastLine & Maps[i - 1]) == 0)
for (int now = 0; now < (1 << m); ++now)
if ((now & (now << 1)) == 0 && (now & (now << 2)) == 0 && (now & Maps[i]) == 0 && (now & lastLine) == 0)
for (int lastedLine = 0; lastedLine < (1 << m); ++lastedLine)
if ((lastedLine & lastLine) == 0 && (lastedLine & now) == 0 && (lastedLine&(lastedLine<< 1) ) == 0 && (lastedLine&(lastedLine<< 2) ) == 0 && (lastedLine & Maps[i - 2]) == 0)
dp[lastLine][now][i% 3] = max(dp[lastLine][now][i% 3], dp[lastedLine][lastLine][(i - 1) % 3] + eachOne[now]);
int ans = 0;
for (int lastLine = 0; lastLine < (1 << m); ++lastLine)
for (int now = 0; now < (1 << m); ++now)
ans = max(ans, dp[lastLine][now][(n - 1) % 3]);
printf("%d", ans);
return 0;
}