题解 CF1312E 【Array Shrinking】

· · 题解

题目

传送门

题解

由于 n\le 500，所以这道题支持类似 \mathcal O(n^3) 之类的小暴力...

发现对于固定的某一段 [l,r]，我们可以直接处理出它们会合并成什么亚子，定义 f[i][j] 为 [i,j] 可以合并成什么数，如果不可行为 -1，否则为合并的值

这里直接给出求 f 的代码，不作过多说明

inline int Merge(const int l,const int r){
    if(l==r)return a[l];
    if(a[l]!=a[l+1])return -1;
    if(l+1==r)return a[l]+1;
    rep(i,l+2,r)if(a[i-1]+1!=a[i])return -1;
    return a[r]+1;
}

inline void Solve_f(){
    rep(i,1,n)rep(j,i,n)f[i][j]=Merge(i,j);
}

然后，我们可以直接进行 dfs，首先定义 memo[i][j] 表示区间 [i,j] 最少会被合并成多少个点，首先我们显然知道，若 f[i][j]\neq -1，那么 memo[i][j]=1，对于其他情况，显然有转移

memo[i][j]=\min \{memo[i][k]+memo[k+1][j]|k\in[l,r-1]\}

但是有一种比较特殊的情况，就是 memo[i][k]=memo[k+1][j]=1 且 f[i][k]=f[k+1][j] 时，我们可以将左右区间合并，即 memo[i][j]=1,f[i][j]=f[i][k]+1，其他情况随便做就可以了...

代码

https://www.cnblogs.com/Arextre/p/13391732.html