Halloween Costumes LightOJ - 1422

区间dp的关键就是分好类

题意：
小灰灰参加圣诞节的一些派对，并且需要穿上对应派对的衣服，所以他需要多次换衣服，为了方便，他可以选择脱掉一些衣服或者穿上新衣服，比如说，他穿着超人的衣服，外面又穿着死侍的衣服，当他要参加超人服装派对时，他可以选择脱掉死侍的衣服（因为死侍衣服的里面有超人的衣服），或者他可以在穿一件超人的衣服，小灰灰是个爱干净的人，当他脱下死侍的衣服后，如果需要再穿死侍的衣服，他会选择再穿一件新的。（如果他先穿A衣服，又穿上B衣服，再穿一件C衣服，如果他想让最外面的衣服是A，他可以选择直接穿一件A，或者先把C脱掉，再把B脱掉）。
分析：
对于[i, j]， 对j进行分类讨论：
-j穿的衣服是新的, dp[i][j] = dp[i][j - 1] + 1
-j穿的衣服是旧的，则最近一次穿一定是由[i, j - 1]中跟j相同的元素转移过来的，详见代码。（最近一次穿是理解转移的关键）
代码：

#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 dp[maxn][maxn];
int n;
int v[maxn];

void init()
{
    for(int i = 1; i <= n; i++)
        dp[i][i] = 1;
}

int main()
{
    int t; cin >> t;
    int cases = 0;
    while(t--)
    {
        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;
                dp[i][j] = dp[i][j - 1] + 1;
                for(int k = i; k < j; k++)
                    if(v[k] == v[j])
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j - 1]);
            }
        printf("Case %d: %d\n", ++cases, dp[1][n]);
    }
}