题解：P5189 [COCI 2009/2010 #5] ZUMA

· · 题解

十分有思维难度的一道区间动规题目。

一开始想到可以设计一个二维的状态，令 dp_{i,j} 表示第 i 位到第 j 位的弹子被全部消除时需要放置的弹子的最少数量，然而很容易发现并不好转移，因为你并不好确定在 j 这个位置之前有多少个数字与 c_j 相同，也就不好确定你究竟要增加多少个弹子。所以考虑增加一个状态。

通过惊人的注意力，我决定加入一个状态，令 dp_{i,j,x} 表示在第 j+1 到第 n 位的与 c_j 颜色不同的弹子已经全部消除时，将第 i 位到第 j 位的弹子以及之后 x 位与 c_j 颜色相同的弹子全部消除需要放置的弹子的最少数量。于是开始转移。

枚举区间长度与 i，再枚举 x，因为显然地，当 x \ge k 时，我不需要添加任何弹子，因此枚举毫无意义，所以只需枚举 [0,k-1] 中的所有数即可。进行初始化，此时 dp_{i,j,x} = dp_{i,j-1,0} + k - x - 1，因为你要先消除第 i 位到第 j-1 位的所有弹子，所花费的代价也就是 dp_{i,j-1,0}，然后再删除第 j 位以及之后 x 位与 c_j 颜色相同的弹子共计 x+1 位弹子，所花费的代价也就是 k - x - 1。当然，这样一般来说不会是最优的，因为在第 i 位到第 j-1 位的弹子中，可能存在颜色与 c_j 相同的弹子，因此枚举 [i,j-1] 中的所有 p，如果 c_j=c_p，那么可以令 dp_{i,j,x} = \min(dp_{i,j,x},dp_{i,p,\min(x+1,k-1)}+dp_{p+1,j-1,0})，后面这串柿子的意思就是先去掉第 p+1 位到第 j-1 位的弹子，然后再去掉第 i 位到第 p 位的弹子及之后的第 j 位以及我们所需要的之后的 x 位，共计 x+1 位。最后就会发现答案已经唾手可得，就是 dp_{1,n,0}。 代码如下。时间复杂度 O(n^3k)。

#include<bits/stdc++.h>
using namespace std;
const int N=105;
using ll=long long;
int dp[N][N][N],c[N],n,m;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int l=1;l<=n;l++){
        for(int i=1;i<=n-l+1;i++){
            int j=i+l-1;
            for(int x=0;x<m;x++){
                dp[i][j][x]=dp[i][j-1][0]+m-x-1;
                for(int k=i;k<j;k++){
                    if(c[k]==c[j]) dp[i][j][x]=min(dp[i][j][x],dp[i][k][min(x+1,m-1)]+dp[k+1][j-1][0]);
                }
            }
        } 
    }
    cout<<dp[1][n][0];
    return 0;
}