- 9.23
- 模拟赛
- 坐牢一个小时就去写其他题了
- T1 DP优化
- 想到了初始的DP状态，但是由于复杂度的 \(O（n^5）\)否掉了自己的做法
- 没有想到好的办法规避这种情况，唯一的方法就是 在时间充足的情况下尽可能地把一种想法想下去
- 第一步肯定是可以想到的 \(f_{i,j,k}\) 表示到 \(i\) 的位置选的元素在 A 赢了会有 \(j\) 的盈利, B 赢了会有 \(k\) 的盈利，C 赢了会有的最大的盈利，去转移
- 而且 正确的思维过程应该在稿纸上体现出来
- 答案是 \(\sum b - \max_{i=1}^{3} (\sum a_i + b_i)\)
- 可以发现我们在选择一个数的时候 \(\sum b\) 会增加，它所对应的 \(\sum a_i + b_i\) 也会增加
- 可以比较自然的发现我们可以在 \(\max_{i=1}^{3} (\sum a_i + b_i)\) 固定的情况下求出 \(sum_b\) 的最大值，所以可以转换为背包问题进行求解
- 模拟赛
