LightOJ-1422 区间dp

题意

小灰灰参加圣诞节的一些派对，并且需要穿上对应派对的衣服，所以他需要多次换衣服，为了方便，他可以选择脱掉一些衣服或者穿上新衣服，比如说，他穿着超人的衣服，外面又穿着死侍的衣服，当他要参加超人服装派对时，他可以选择脱掉死侍的衣服（因为死侍衣服的里面有超人的衣服），或者他可以在穿一件超人的衣服，小灰灰是个爱干净的人，当他脱下死侍的衣服后，如果需要再穿死侍的衣服，他会选择再穿一件新的。（如果他先穿A衣服，又穿上B衣服，再穿一件C衣服，如果他想让最外面的衣服是A，他可以选择直接穿一件A，或者先把C脱掉，再把B脱掉）。

题解

/*
O(n3)
区间dp
dp起点为起点和终点相同的为1
然后开始枚举中间点，
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
如果起点和终点的值一样就在枚举前设置
dp[i][j]=dp[i][j-1]
*/
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <cstdio>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 240;
int n;
int num[maxn], dp[maxn][maxn];
int main()
{
    ios::sync_with_stdio(0);
    // freopen("a.in", "r", stdin);
    int __t, dd = 1;
    cin >> __t;
    while (__t--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> num[i];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = 0x3f3f3f3f;
        for (int i = 1; i <= n; i++)
            dp[i][i] = 1;

        for (int len = 1; len < n; len++)
        {
            for (int i = 1; i + len <= n; i++)
            {
                int j = i + len;
                if (num[i] == num[j])
                    dp[i][j] = dp[i][j - 1];
                for (int k = i; k < i + len; k++)
                {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                }
            }
        }
        cout << "Case " << dd++ << ": " << dp[1][n] << endl;
    }

    return 0;
}