补题记录——Oct. Training 2

题意

一个n * n的方阵中有n个怪兽，每个怪兽对应一个val值，一个技能可以打死一行或一列的所有怪兽，问最多用三次这个技能，打死怪兽的价值和最大是多少。

思路

对于每行每列 我们都先预处理出怪兽的价值和。
三次操作只有四种可能：三行、三列、一行两列、一列两行，前两种可以先特判一下，主要是后面两种情况，如果直接枚举行和列会超时，
可以注意到假如我们选定一行为被使用技能的，然后找该行上所有点出现过的列（没出现过就不用），然后对于这样的列 列值和都减去在这列在该行上的
点值 取处理后列值和最大的两列就是我们选择该行的情况下，选择列的最优解。
对于求价值和最大的两个列，我们可以用multiset处理，键值自动排序来降低复杂度，每次删除先用find找到位置再删就好了 然后操作完一行再复原以免影响后续操作。
按这样枚举每行 和每列 复杂度是两倍点的个数

#include<bits/stdc++.h>
#include<unordered_map>
#include<array>
#define ll long long
#define ull unsigned long long
#define all(a) a.begin(),a.end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;
const ll mod = 1e9 + 7;
const int N = 1e6 + 5;
const int maxn = 1e5 + 10;

int n, visr[N], visc[N], valr[N], valc[N];
map<pair<int, int>, int>mp;
//rr: 每行有那些列 cc: 每列有哪些行， r： 行序号 c： 列序号
vector<int>rr[N], cc[N], r, c;
//st1: 行值和 st2: 列值和
multiset<int, greater<>>st1, st2;

void solve()
{
	cin >> n;
	int x, y, v;

	for (int i = 1; i <= n; i++) {
		cin >> x >> y >> v;
		mp[{x, y}] = v;
		if (!visr[x]) r.emplace_back(x);
		if (!visc[y]) c.emplace_back(y);
		valr[x] += v;
		valc[y] += v;
		visr[x] = visc[y] = 1;
		rr[x].emplace_back(y);
		cc[y].emplace_back(x);
	}

	for (auto x : r) st1.insert(valr[x]);
	for (auto x : c) st2.insert(valc[x]);

	int ans = 0, x1 = 0, x2 = 0;
	auto t = st1.begin();
	auto t2 = st2.begin();
	for (int i = 1; i <= 3 && t != st1.end(); i++) {
		x1 += *t;
		t++;
	}
	for (int i = 1; i <= 3 && t2 != st2.end(); i++) {
		x2 += *t2;
		t2++;
	}

	ans = max({ ans, x1, x2 });

	for (auto& i : r) {
		for (auto& j : rr[i]) {
			st2.erase(st2.find(valc[j]));
			st2.insert(valc[j] - mp[{i, j}]);
		}

		int x1 = 0;
		auto t = st2.begin();
		for (int i = 1; i <= 2 && t != st2.end(); i++) {
			x1 += *t;
			t++;
		}
		ans = max(ans, valr[i] + x1);

		for (auto& j : rr[i]) {
			st2.erase(st2.find(valc[j] - mp[{i, j}]));
			st2.insert(valc[j]);
		}
	}

	for (auto& i : c) {
		for (auto& j : cc[i]) {
			st1.erase(st1.find(valr[j]));
			st1.insert(valr[j] - mp[{j, i}]);
		}

		int x1 = 0;
		auto t = st1.begin();
		for (int i = 1; i <= 2 && t != st1.end(); i++) {
			x1 += *t;
			t++;
		}
		ans = max(ans, valc[i] + x1);

		for (auto& j : cc[i]) {
			st1.erase(st1.find(valr[j] - mp[{j, i}]));
			st1.insert(valr[j]);
		}
	}

	cout << ans << "\n";
}

signed main()
{
	IOS;
	int _t = 1;
	//cin >> _t;
	while (_t--)
		solve();
	return 0;
}

原文地址：http://www.cnblogs.com/yaqu-qxyq/p/16810094.html