51NOD-1625 夹克爷发红包 题解

题目大意

给你一个$n*m$的矩阵，矩阵中存在初始值，现在你可以进行$k$次操作，将任意一行或者一列每一个数都赋值为$x$，问你矩阵最大和为多少。

解题思路

刚开始我是想，用贪心，计算出每一行，每一列的修改值，然后从小到大的修改。

想了想，发现很麻烦，而且还不一定正确。。

直接懵了，想了好久，没想出来。。

去看了题解。。

用状态压缩的方法，枚举每一行的情况，因为n的范围不大，最大也就是$2^{10}$。

状压，用我自己的话来说，就是用一个数的二进制来表示每一位的情况，所以说其实是相当暴力的。

可以用这一位为1来表示选，为0的表示不选。

因为行确定了，而列与列之间不会互相影响，这样只需要枚举出最大值即可。

（这方法好妙啊。。

完整代码

#include <iostream>
#include <functional>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;
ll num[20][300],dx[300];

int main() {
	int n, m, x, k;
	cin >> n >> m >> x >> k;
	ll sum = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)	
			cin >> num[i][j],sum+=num[i][j];
	}
	ll ans = sum;
	for (int i = 0; i < (1 << n); i++) {
		ll res, cnt;
		res = cnt = 0;
		for (int j = 1; j <= n; j++) {
			if (i & (1<<(j-1))) {//判断第j位是不是为1
				cnt++;
				for (int g = 1; g <= m; g++)	res += x - num[j][g];
			}
		}
		if (cnt > k)	continue;
		cnt = k - cnt;
		memset(dx, 0, sizeof(dx));
		for (int j = 1; j <= m; j++) {
			for (int g = 1; g <= n; g++) {
				if (i & (1 << (g - 1)))	continue;
				dx[j] += x - num[g][j];
			}
		}
		sort(dx + 1, dx + 1 + m, greater<ll>());//十年OI一场空，不开longlong见祖宗，我又忘了。。
		for (int j = 1; j <= m && j <= cnt; j++) {
			if (dx[j] < 0)	break;
			res += dx[j];
		}
		ans = max(ans, sum + res);
	}
	cout << ans << endl;
}