题解：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

个本来就存在的弹子合并消除了，所需要添加的弹子数量。可以写出转移：

直接消除 $j$ 和后面的 $x$ 个： $f_{i,j,x}=f_{i,j-1,0}+\max(0,k-x-1)$ 。
假设 $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)

。

代码

CPP

#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;
}

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

文章操作

做法

代码

相关推荐

评论

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