## 赌局
#背包dp #容斥 #贪心
如果我们已经选择了一种方案（以下 $a,b$ 表示已选的），那么我们可以枚举最终是哪个人赢了，赌除了这个人以外的人的就要给你钱，赌了这个人的你就要给他钱，因此最坏情况下收益为
$
\min\limits_{i\in [1,3]}\left(\underbrace{\sum\limits_{j\ne i}b_j}_\text{输的人给你的}-\underbrace{\sum a_i}_\text{赢的人你给的}\right)
$
很显然 $j\ne i$ 求和那里不好处理，但是我们可以做容斥，用所有 $b$ 的和减去 $\sum b_i$，因此问题变成
$
\min\limits_{i\in [1,3]}\left(\sum b-\sum b_i-{\sum a_i}\right)=\min\limits_{i\in [1,3]}\left(\sum b-\sum(a_i+b_i)\right)
$
而已选的 $b$ 的和在统计答案时其实是常数，因此我们需要最大化 $\sum(a_i+b_i)$，即求
$
\sum b-\max_{i\in[1,3]}\sum(a_i+b_i)
$
但是这个 $\max$ 很难处理，因为我们并不清楚三个当中的哪一个才是 $\max$。而我们选择一个新的元素时，可能会改变 ${} \max\sum(a_i+b_i) {}$，也会导致 $\sum b$ 变化，这个变化是很难维护的。
因此我们需要将 $\max\sum(a_i+b_i)$ 作为限制，也就是限制三组当中的任何一组都要满足 $\sum(a_i+b_i)$ 不超过这个值，而在满足条件的情况下最大化 $\sum b$。
于是我们可以对每一组做 0/1 背包。将 $a_i+b_i$ 视为重量，$b_i$ 视为价值，这样子我们就可以得到在重量不超过一定值的情况下，价值的最大值，也就是上式的要求。
因此思路就很清晰了。
1. 对每一组做以 $a_i+b_i$ 为重量，$b_i$ 为价值的 0/1 背包；
2. 对背包做前缀 $\max$，得到重量不超过限制的最大价值（如果 dp 数组全初始化为 $0$ 就可以省略这一步）；
3. 枚举 $\sum(a_i+b_i)$ 的最大值，在每一组都不超过这个限制的情况下计算最大 $b_i$ 和。
时间复杂度 $\mathcal O(n\times nV)$。
```cpp
#include <iostream>
#include <vector>
using namespace std;
using LL = long long;
const LL kMaxN = 505 * 505 + 5;
struct Node {
LL a, b;
};
LL dp[4][kMaxN], n, ans;
vector<Node> v[4], itm;
// 01 背包
void solve(LL dp[kMaxN], const vector<Node> &itm) {
for (auto i : itm) {
for (LL j = kMaxN - 1; j >= i.a; j--) {
dp[j] = max(dp[j], dp[j - i.a] + i.b);
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (LL i = 1, t, a, b; i <= n; i++) {
cin >> t >> a >> b;
v[t].push_back(Node{a, b});
}
for (LL i = 1; i <= 3; i++) {
itm.clear();
// 按照上述方式构建背包元素
for (auto j : v[i]) {
itm.push_back(Node{j.a + j.b, j.b});
}
solve(dp[i], itm);
}
for (LL i = 0; i < kMaxN; i++) { // 枚举 sum(a[i]+b[i]) 的最大值
LL sum = 0;
for (LL j = 1; j <= 3; j++) { // 枚举分组
sum += dp[j][i]; // 在 sum(a[i]+b[i]) 不超过最大值的情况下求 b[i] 最大和
}
ans = max(ans, sum - i); // 注意这里和式子一样要减最大值
}
cout << ans << '\n';
return 0;
}
```
## 三元组
写了个 $\mathcal O(n^2)$ 的暴力，光荣获得 $10$ 分。
## 游戏
啥都没写。
## 连通性统计
啥都没写。
## 总结
总分：$100+10=110$。
花了两个多小时写了 T1，然后 T2 没怎么想就只写了暴力，后两题根本没动。还是相较于上次有进步，至少成功地写出了 T1 捍卫了最后的尊严，但是后面去写美丽的 CCH 题单了就没做了，其实还可以骗得更多分数。T2 正解好像也不是很复杂，等会看看。