- 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\) 的最大值,所以可以转换为背包问题进行求解
- 模拟赛