lightoj 1422

题意：要参加n天的party，每天指定要穿什么衣服，衣服叠加穿但是一但脱下来就不能再穿上去

问最少需要准备几件衣服。

首先要知道当a[i]==a[j]时即第i天与第j天要穿的衣服一样时，第j天最少要穿的衣服数是第j-1天所要穿的衣服数

只要把前面穿的别的衣服脱下来就行了。当然也可以考虑继续穿上一件这样的衣服，显然这样在i~j天内就不是最

优解。我们可以用区间来解决这个问题，就如上面说的，在i~j区间就这样考虑然后再推广到1~n的区间，这样就

是标准的区间dp了

#include <iostream>
#include <cstring>
using namespace std;
int a[110];
int dp[110][110];
int main() {
    int t;
    cin >> t;
    int ans = 0;
    while(t--) {
        ans++;
        int n;
        cin >> n;
        for(int i = 1 ; i <= n ; i++)
            cin >> a[i];
        memset(dp , 0X3f3f3f3f , sizeof(dp));
        for(int i = 1 ; i <= n ; i++) {
            for(int j = i ; j <= n ; j++) {
                dp[i][j] = j - i + 1;
            }
        }
        for(int i = 1 ; i < n ; i++) {
            for(int j = 1 ; j <= n && i + j <= n ; j++) {
                if(a[j] == a[i + j]) {
                    dp[j][i + j] = min(dp[j][i + j] , dp[j][i + j - 1]);
                }
                for(int k = j ; k < i + j ; k++) {
                    dp[j][i + j] = min(dp[j][i + j] , dp[j][k] + dp[k + 1][i + j]);
                }
            }
        }
        cout << "Case " << ans << ": ";
        cout << dp[1][n] << endl;
    }
    return 0;
}