这题为什么不可以用DP
查看原帖
这题为什么不可以用DP
767561
Ascnbeta楼主2024/9/21 19:10

附代码

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[205],b[205],ans = INT_MAX;
int res[205][205],bres[205][205],res1[205][205];
int dp[205][205];
int Bit (int x) {
	int t = x,ret = 0;
	while(t) {
		if (t&1) ++ret;
		t /= 10;
	}
	return ret;
}
int main () {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= m; i++) cin >> b[i];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			res[i][j] = a[i] & b[j];
			int temp = res[i][j],base = 1,y = 0;
			while(temp) {
				int x = temp % 2;
				y += x * base;
				base *= 10;
				temp /= 2;
			}
			bres[i][j] = y;
//			res1[i][j] = Bit(bres[i][j]);
		}
	}
//	for (int i = 1; i <= n; i++) {
//		for (int j = 1; j <= m; j++) {
//			cout << res[i][j] << ' '; 
//		}
//		cout << "\n";
//	}
//	for (int i = 1; i <= n; i++) {
//		for (int j = 1; j <= m; j++) {
//			cout << bres[i][j] << ' '; 
//		}
//		cout << "\n";
//	}
//	for (int i = 1; i <= n; i++) {
//		for (int j = 1; j <= m; j++) {
//			cout << res1[i][j] << ' '; 
//		}
//		cout << "\n";
//	}
	memset(dp,0x3f,sizeof(dp));
	for (int j = 1; j <= n; j++) {
		for (int k = 1; k <= m; k++) {
			if (j == 1) {
				dp[j][k] = res[n][k];
			}else{
				dp[j][k] = min(dp[j][k],(dp[j-1][k]|res[j][k]));
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cout << dp[i][j] <<' ';
		}
		cout <<'\n';
		
	}
	for (int i = 1; i <= m; i++) {
		ans = min(ans,dp[n][i]);
	}
	cout << ans << endl;
	return 0;
} 

过不了样例3

2024/9/21 19:10
加载中...