为什么第一步一定要枚举子集?
查看原帖
为什么第一步一定要枚举子集?
943083
wfc284楼主2025/1/27 21:55

rt,预处理的时候要算出【aia_i 操作 jj 次达到的最小值】,为什么下面的 O(nm2)O(nm^2) greedy 是错的:

for(int i = 1; i <= n; ++i) {
			memset(used, 0, sizeof(used));
			int tmp = a[i];
			for(int x = 1; x <= m; ++x) {
				int mx = -Linf, pos = 0;
				for(int j = 1; j <= m; ++j)
					if(!used[j] && tmp - (tmp & b[j]) > mx)
						mx = tmp - (tmp & b[j]), pos = j;
				tmp -= mx;
				v.push_back(mx), used[pos] = 1;
			}
		}

求大佬指教。

只能枚举子集。

2025/1/27 21:55
加载中...