Array Shrinking CodeForces - 1312E | 区间dp

首蓝不易。

题意：
略
分析：
区间dp的状态转移可以从母状态入手，通过分析母状态的所有可能情况，去寻找子状态。比如：
对于一段[l, r]， 他最后可能只剩下1个，也可能2个、3个。。。，对于1个来说，他一定能找到两个子状态压缩之后长度为1且元素相等；对于多个来说，他一定能找到两个子状态分别压缩之后两个结合时不能再压缩。于是可以得到转移方程。
代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
const ll mod = 1e9 + 7;
const int maxn = 1e3;
const int inf = 0x3f3f3f3f;
int v[maxn];
int dp[maxn][maxn];
int final[maxn][maxn];//记录该区间压缩为1个元素之后元素的值
int n; 
void init()
{
    for(int i = 1; i <= n; i++)
        for(int j = i; j <= n; j++)
            dp[i][j] = i == j ? 1 : j - i + 1;
    for(int i = 1; i <= n; i++) final[i][i] = v[i];
}

int main()
{
   cin >> n;
   for(int i = 1; i <= n; i++) cin >> v[i];
   init();
   for(int len = 2; len <= n; len++)
    for(int i = 1; i + len - 1 <= n; i++)
    {
        int j = i + len - 1;
        for(int k = i; k < j; k++)
        {
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
            if(dp[i][k] == 1 && dp[k + 1][j] == 1 && final[i][k] == final[k + 1][j])
                dp[i][j] = 1, final[i][j] = final[i][k] + 1;
        }
    }
    cout << dp[1][n] << endl;
}