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

· · 题解

做法

我写的详细一点。

每次消除一个区间，很容易让人想到用 f_{i,j} 表示将 i \sim j 这一段消除，所需要添加的弹子数量。转移的时候，想要把 j 消除，要么是将 j 单独添加一些弹子消除，要么与 i \sim j-1 的一些同色弹子合并，再添加一些弹子消除。

但是当我们要将 j 和前面的一些弹子合并消除的时候，没法知道之前还剩下几个同色弹子，就没法知道要添加多少了。如果新增状态表示之前弹子的情况，状态数就炸了。

如果能构造一个状态，使得这次合并在前面与 j 合并的那个弹子的位置就被预料到并且计算了花费，然后在处理 i \sim j 这一段的时候再调用，问题就解决了。

使用 P2135 中的技巧，f_{i,j,x} 表示将 i \sim j 这一段消除，并且未来 j 与后面的 x 个本来就存在的弹子合并消除了，所需要添加的弹子数量。可以写出转移：

  1. 直接消除 j 和后面的 x 个：f_{i,j,x}=f_{i,j-1,0}+\max(0,k-x-1)。

  2. 假设 c_p=c_j，将 j 和后面的 x 个与 p 合并：f_{i,j,x}=f_{i,p,x+1}+f_{p+1,j-1,0}。

那为什么只需要考虑 j 和后面的弹子合并，不需要考虑 i \sim j-1 的弹子和后面的弹子合并呢？借用一下 2009 集训队论文 徐源盛 《对一类动态规划问题的研究》中的一段话。

这样已经可以过了，但 \geq K 个弹子合并都不需要额外添加弹子，所以 dp 数组的第三维其实只用算到 K-1 即可。最终时间复杂度 O(N^3 K)。

代码

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define i128 __int128
#define ALL(x) x.begin(),x.end()
#define popcount(x) __builtin_popcountll(x)
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
const int INF=1e18;
const int N=105;
const int MOD=1e9+7,MOD2=998244353;
int n,k,a[N],f[N][N][6];//和j后面本来就存在的k个一起消除
void solve_(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int len=1;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int j=i+len-1;
            for(int x=0;x<k;x++){
                f[i][j][x]=f[i][j-1][0]+max(0ll,k-x-1);
                for(int p=i;p<j;p++){
                    if(a[p]==a[j]){
                        f[i][j][x]=min(f[i][j][x],f[i][p][min(k-1,x+1)]+f[p+1][j-1][0]);
                    }
                }
            }
        }
    }
    cout<<f[1][n][0]<<"\n";
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase,multitest=0;
    if(multitest)cin>>testcase;
    else testcase=1;
    while(testcase--){
        solve_();
    }
    return 0;
}