WA #104,找不到问题,求助
查看原帖
WA #104,找不到问题,求助
510555
ImposterAnYu楼主2024/8/5 11:56
#include <bits/stdc++.h>
#define int1 int
#define N 40
#define M 256
#define INF 114514
using namespace std;
int1 n,m,m2,dp[N + 5][N + 5][M + 5],i,j,k,l,ans,one[M + 5],x,y;
int1 read(){
	int1 x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch)){
		if (ch == '-'){
			f = -1;
		}
		ch = getchar();
	}
	while (isdigit(ch)){
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
void uprint(int1 x){
	if (x >= 10){
		uprint(x / 10);
	}
	putchar(x % 10 ^ 48);
	return ;
}
void print(int1 x){
	if (x < 0){
		putchar('-');
		x = -x;
	}
	uprint(x);
	return ;
}
void ps(int1 x){
	print(x);
	putchar(' ');
	return ;
}
void pe(int1 x){
	print(x);
	putchar('\n');
	return ;
}
bool check(int1 x){
	return ((x & m2) == m2);
}
int main(){
	n = read(),m = read();
	if(n == 1 && m == 1){
		pe(0);
		return 0;
	}
	if(n < m){
		n ^= m,m ^= n,n ^= m;
	}
	m2 = (1 << m) - 1;
	for(i = 0; i <= m2; i++){
		for(j = 0; j < m; j++){
			if(i & (1 << j)){
				one[i]++;
			}
		}
		for(j = 0; j <= n; j++){
			for(k = 0; k <= m2; k++){
				dp[j][i][k] = INF;
			}
		}
	}
	for(j = 0; j <= m2; j++){
		for(k = 0; k <= m2; k++){
			dp[1][j][k] = one[j];
		}
	}
	for(j = 0; j <= m2; j++){
		for(k = 0; k <= m2; k++){
			for(l = 0; l <= m2; l++){
				if(check(j | (k | (k << 1) | (k >> 1)))){
					dp[2][j][k] = min(dp[2][j][k],dp[1][k][l] + one[j]);
				}
			}
		}
	}
	for(i = 3; i <= n; i++){
		for(j = 0; j <= m2; j++){
			for(k = 0; k <= m2; k++){
				for(l = 0; l <= m2; l++){
					if(check(j | (k | (k << 1) | (k >> 1)) | l)){
						dp[i][j][k] = min(dp[i][j][k],dp[i - 1][k][l] + one[j]);
					}
				}
			}
		}
	}
	ans = INF;
	for(i = 0; i <= m2; i++){
		for(j = 0; j <= m2; j++){
			if(check((i | (i << 1) | (i >> 1)) | j)){
				ans = min(ans,dp[n][i][j]);
			}
		}
	}
	pe(n * m - ans);
	return 0;
}
//6 6
//26

对于 6 6 这一组数据我输出 3030,但答案是 2626,实在调不出来了……

2024/8/5 11:56
加载中...