Unknown__ @ 2023-08-03 17:29:01
如果不用特判,怎样过hack数据啊? 以下为100分wa代码
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int f[1 << 20],dp[110][1 << 10][1 << 10],n,m,A[101010],tot,pos[1 << 20];
signed main()
{
cin>>n>>m;
int i,j,k,l,o;
for(i = 1;i <= n;i++)
for(j = 0;j < m;j++)
{
char c;cin>>c;
if(c == 'H')A[i] |= (1 << j);
}
for(i = 0;i < (1 << m);i++)
if(!(i & (i << 1)) && !(i & (i << 2)))
{
f[++tot] = i;
for(int t = i;t;t -= t & (-t))pos[tot]++;
}
for(i = 1;i <= tot;i++)
if(!(A[1] & f[i]))
dp[1][i][0] = pos[i];
for(i = 1;i <= tot;i++)
if(!(A[2] & f[i]))
for(j = 1;j <= tot;j++)
if(!(f[i] & f[j]))
dp[2][i][j] = pos[i] + pos[j];
for(i = 3;i <= n;i++)
for(j = 1;j <= tot;j++)
if(!(A[i] & f[j]))
for(k = 1;k <= tot;k++)
if(!(f[j] & f[k]) && !(f[k] & A[i - 1]))
for(l = 1;l <= tot;l++)
if(!(f[l] & f[k]) && !(f[l] & f[j]) && !(f[l] & A[i - 2]))
dp[i][j][k] = max(dp[i][j][k],dp[i - 1][k][l] + pos[j]);
int ans = 0;
for(i = 1;i <= tot;i++)
for(j = 1;j <= tot;j++)
ans = max(ans,dp[n][i][j]);
cout<<ans;
}
by Unknown__ @ 2023-08-03 17:30:36
(还是说这就是一种极端情况,必须特判
by Austra @ 2023-08-08 10:31:56
不用特判,起码我没有