【2024.10.4 闲话】0/99+

今日推歌：没有。明天可能有。
今日 set：也没有。话说应该没人知道 set 是什么吧，总之不是 std::set。

[ARC176E] Max Vector

给你两个长度为 \(N\) 的正整数序列： \(X=(X_1,X_2,\dots,X_N)\) 和 \(Y=(Y_1,Y_2,\dots,Y_N)\) 。
此外，你还得到 \(M\) 个长度为 \(N\) 的正整数序列。第 \(i\) 个序列是 \(A_i = (A_{i,1},A_{i,2},\dots,A_{i,N})\) 。
对于每个 \(i = 1,2,\dots,M\)，您必须对每个 \(i\) 执行下列操作中的一种。

• 对于所有 \(1 \le j \le N\), \(X_j\) 替换为 \(\max(X_j,A_{i,j})\)。
• 对于所有 \(1 \le j \le N\)，\(Y_j\) 替换为 \(\max(Y_j,A_{i,j})\)。

求所有操作后 \(\sum_{j=1}^{N} (X_j + Y_j)\) 的能达到的最大值。
\(1\leq n\leq 10,1\leq m,A_i,X_i,Y_i\leq 500\)。

?

可以将 \(\max\) 转化为选择对 \(X_j/Y_j\) 是否赋值，且每个位置只能被赋值一次，每个序列只能对 \(X,Y\) 中的一个赋值。
不难写出 \(O(2^{2N}NM)\) 的 dp。过不了。怎么会事呢？
点开题解，发现自己看错题目了😅😅😅。

求所有操作后 \(\sum_{j=1}^{N} (X_j + Y_j)\) 的能达到的最小值。

如果求最小值的话，那不就变成经典最小割模型了吗。那不就做完了吗。

但我仍然在想，如果是求最大值的话，肯定有很多个值用不上，是不是可以找到一种方法把这个 \(M\) 优化掉呢？
可惜，这是我最不擅长的。但是 ??? 说：

• 显然，对于每个 \(i\),\(A_{*,i}\) 中前 \(N\) 大的数才是有用的，因为一个序列最多被赋值 \(N\) 次；在最优方案中，\(X_i/Y_i\) 的最终值一定大于等于 \(A_{*,i}\) 中前 \(N+1\) 大的数。
• 这样，有用的位置只有 \(O(N^2)\) 个，只要对于这些位置进行转移就行了，时间复杂度 \(O(2^{N}N^2)\)。

明明积累了那么多道题，在考场上为什么却想不出来呢？就像在 spellcard practice 中总是能收卡，在实战中却 0/99+ 一样。
我尝试去追赶他。我什么时候能做到像他一样快，一样强。或许到了某一天，即便没有追上，我也会成为 master 呢（见摘要）。