主要讲一下每一题的做法以及思考方式。
感觉难度薇 \(T1-T3-T2\) 。但是都不算难。
\(T1\)
题目描述
Jimmy 最近迷上了一款叫做方块消除的游戏。游戏规则如下：\(n\) 个带颜色方格排成一列，相同颜色的方块连成一个区域（如果两个相邻方块颜色相同，则这两个方块属于同一区域）。为简化题目，将连起来的同一颜色方块的数目用一个数表示。
例如，9 122233331 表示为
4
1 2 3 1
1 3 4 1
游戏时，你可以任选一个区域消去。设这个区域包含的方块数为 \(x\)，则将得到 \(x^2\) 个分值。方块消去之后，其余的方块就会竖直落到底部或其他方块上。而且当有一列方块被完全消去时，其右边的所有方块就会向左移一格。Jimmy 希望你能找出得最高分的最佳方案，你能帮助他吗？
第一行包含一个整数 \(m\)（\(1 \le m \le 50\)），表示同颜色方块区域的数目。
第二行包含 \(m\) 个数，表示每个区域的颜色（\(1\) 到 \(m\) 之间的整数）。
第三行包含 \(m\) 个数，表示每个区域包含的方块数（\(1\) 到 \(20\) 之间的整数）。
思路点拨
挺简单的一题。考虑到本题从序列中间开始操作会得到不同的结果，所以不可以使用类似于子序列提取的线性dp,而是考虑区间dp。
我们比较头疼的是，在消除完之后右边的方块会挪过来，所以我们可以在状态中体现这一点。我们定义 \(f_{l,r,k}\) 表示是目前考虑了区间 \(l,r\) 的方格，右端点右边接了 \(k\) 个与之颜色相同过的方块的最大价值。
转移分两类讨论：
- 把右边炸了！
\[f_{l,r,k}=f_{l,r-1,0}+(num[r]+k)^2
\]
- 考虑炸掉中间一段，然后右边的 \((num[r]+k)\) 移到左边去（要求左边与右边颜色相同）
\[f_{l,r,k}=f_{l,mid,num[r]+k}+f_{mid+1,r-1,0}
\]
别的不需要多多考虑，因为我们最为简单的方式就是从左到右依次炸掉，我们不论怎么操作，答案不会劣于这个。所以我们只需要考虑让颜色相同的尽量在一起炸掉。