Array Shrinking

题目链接
动态规划/区间DP

Description

给定一个数组，若数组中相邻的两个数相同(设都为 $a$ )，则它们合并为一个数，其值为 $a + 1$ 。求合并后数组的最小长度。

Solution

考虑区间 $DP$ , 设 $dp[l][r]$ 表示区间 $[l,r]$ 合并后的最小长度，并设 $w[l][r]$ 表示区间 $[l,r]$ 合并后的和
状态转移方程： $dp[l][r] = \min(dp[l][r], dp[l][mid] + dp[mid + 1][r])$
若 $dp[l][mid] = dp[mid + 1][r] = 1$ ，并且 $w[l][mid] = w[mid + 1][r]$ ，则 $dp[l][r] = 1，w[l][r] = w[l][mid] + 1$

Code

Array Shrinking

#include<bits/stdc++.h>
#define boost std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

using namespace std;
using LL = long long;

constexpr int MAXN = 505;
constexpr LL M = 998244353;

int n, a[MAXN], dp[MAXN][MAXN], w[MAXN][MAXN];

template <typename T> inline void read(T &x) {
    int f = 1; x = 0;
    char ch = getchar();
    while (!isdigit(ch)) f = (ch == '-') ? -1 : 1, ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

int main() {
    boost;
    cin >> n;
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 1; i <= n; i++) cin >> a[i], dp[i][i] = 1, w[i][i] = a[i];
    for (int len = 2; len <= n; len++)
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            for (int mid = l; mid < r; mid++) {
                dp[l][r] = min(dp[l][r], dp[l][mid] + dp[mid + 1][r]);
                if (dp[l][mid] == 1 && dp[mid + 1][r] == 1 && w[l][mid] == w[mid + 1][r])
                    dp[l][r] = 1, w[l][r] = w[l][mid] + 1;
            }
        }
    cout << dp[1][n] << endl;
    return 0;
}