CF 1312 E. Array Shrinking

给你一个数组，可以执行如下操作：

  • 选择一对值相同x的相邻元素
  • 将他们替换为值为x + 1的一个元素

每次操作后，数组长度会减1。问数组的最小可能长度是多少？
输入：
第一行一个整数n(1 <= n <= 500)表示数组长度
第二行包括n个整数，以空格隔开
输出：
一个整数表示任意执行上述操作后可以获得的最小长度

思路：
区间DP
dp[i][j]表示从i到j经过合并后的最小长度
f[i][j]表示若从i到j经过合并后长度为1，则合并后的数为f[i][j]

  1. static final int N = 505, INF = 0x3f3f3f3f;
  2. static int[][] dp = new int[N][N], f = new int[N][N];
  3. static int n;
  4. static void solve() {
  5.     n = ni();
  6.     for (int i = 1; i <= n; i++) {
  7.         dp[i][i] = 1;
  8.         f[i][i] = ni();
  9.     }
  11.     for (int len = 2; len <= n; len++) {
  12.         for (int i = 1; i + len - 1 <= n; i++) {
  13.             int j = i + len - 1;
  14.             dp[i][j] = INF;
  15.             for (int k = i; k < j; k++) {
  16.                 if (dp[i][k] + dp[k + 1][j] < dp[i][j]) {
  17.                     dp[i][j] = dp[i][k] + dp[k + 1][j];
  18.                     if (dp[i][k] == 1 && dp[k + 1][j] == 1 && f[i][k] == f[k + 1][j]) {
  19.                         dp[i][j] = 1;
  20.                         f[i][j] = f[i][k] + 1;
  21.                     }
  22.                 }
  23.             }
  24.         }
  25.     }
  26.     out.println(dp[1][n]);
  27. }