今日推歌:没有。明天可能有。
今日 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。过不了。怎么会事呢?
点开题解,发现自己看错题目了