[南海云课堂] [区间 DP] 最小值

· · 个人记录

题意

给定一个长度为 n 的数组 a（1<=n<=500），每次可以进行如下的两步操作：

  1. 选择第 i 个元素 a_i，并且需要满足 a_i=a_{i+1}。

  2. 将 a_i 和 a_{i+1} 替换成 a_i+1。

每次操作很显然会使数组的长度减少 1，问经过若干次操作后数组的长度最小值。

思路

显然，序列可分为若干个区间，两个小区间也可以合成大区间。

再观察 n 的大小，一眼区间 \rm{DP}，不妨往这方面探索。

那么区间的状态如何表示？结合题目，定义 f_{i,j} 表示区间 (i,j) 是否可经过若干次操作使得剩下一个数。

之所以之关注剩下 1 个数的状态，是因为剩下 k 个数的有效区间均可被分为若干个剩下 1 个数的区间。换言之，只剩 1 个数的状态是最小状态。

显然，只记录 f 是不行的。为了判断可否进行操作 2，再定义 jl_{i,j} 表示区间 (i,j) 所剩下的那一个数。

状态有了，转移方程便非常明显。

若满足：

f_{i,k}=1$ ， $f_{k+1,j}=1$，$jl_{i,k}=jl_{k+1,j}

则说明 (i,j) 可由 (i,k) 与 (k+1,j) 转移而来，即：

f_{i,j}=1$，$jl_{i,j}=jl_{i,k}+1

区间 \rm {DP} 部分结束。

定义 g_i 表示 (1,i) 至少剩下几个数。

易发现，如果 f_{j,i}=1，则 g_i=g_{j-1}+1。

最终输出 g_n 即可。

时间复杂度：O(n^3+n^2)。

正确性：由于 f 记录的是最小状态，所以一定能表示出所有有效区间，所以不会漏算、少算。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e2+5;
int n,a[N],f[N][N],jl[N][N],g[N],ans;
int main(){
    cin>>n;
    for(int i=1; i<=n;i++){
        scanf("%d",&a[i]);
        f[i][i]=1;
        jl[i][i]=a[i];
    }
    for(int len=2; len<=n;len++){
        for(int i=1; i<=n-len+1;i++){
            int j=i+len-1;
            for(int k=i; k<=j;k++){
                if(f[i][k]&&f[k+1][j]&&jl[i][k]==jl[k+1][j]){
                    f[i][j]=1;
                    jl[i][j]=jl[i][k]+1;
                }
            }
        }
    }
    ans=n;
    for(int i=1; i<=n;i++){
        g[i]=i;
        for(int j=1; j<=i;j++){
            if(f[j][i]){
                g[i]=min(g[i],g[j-1]+1);
            }
        }
    }
    cout<<g[n];
    return 0;
}