Modern Art 3 (USACO Gold 2021 February)

Modern Art 3 (USACO Gold 2021 US Open)

要仔细分析最优画法的特性。初看这个结构比较像一个堆栈，上层的颜色盖住下层的，但堆栈在这里用起来应该不方便，因为一种颜色可能出现一次，二次，或者任意多次。

回到问题本身，我们要求的东西其实比较简单，只是要画的最少次数。从次数角度考虑，一个最优的画法有以下特点：

将被同一笔画出来、且留到最后的多个相同数字列出来，相邻的中间画线。如果一共有 $K$ 条线那么总的需要画的次数就是 $N-K$ 。

例如：

        1
      4---4
    3-------3
  2-----------2
1---------------1 6
       K=4

所以可以认为每有一条这样的线，就是节省一次。我们使用range DP合并两段连续子序列需要画的次数为一段，只需要当大的序列的左右端点是同一个数字的时候，合并时总需要的次数减一就可以了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
int a[305];
int dp[305][305];
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < n-j; i++) {
            if (j == 0) {
                dp[i][i+j] = 1;
                continue;
            }
            dp[i][i+j] = n;
            for (int k = i; k < i+j; k++) {
                // [i,k], [k+1,i+j]
                dp[i][i+j] = min(dp[i][i+j], dp[i][k] + dp[k+1][i+j] 
                                 - (a[i]==a[i+j] ? 1 : 0));
            }
        }
    }
    printf("%d", dp[0][n-1]);
    return 0;
}