一个问题
查看原帖
一个问题
357237
Unknown__楼主2023/8/3 17:29

如果不用特判,怎样过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;
}
2023/8/3 17:29
加载中...