想不出来的题目

Halloween Costumes（区间dp）

题意：Gappu有n个parties要参加，每个party需要穿对应的服装，每个party之前Gappu可以穿上跟即将到来的party对应的衣服，或者脱掉若干衣服直到最上面的衣服跟party相对应，并且脱掉的衣服就不能再穿。

Sample Input

2

4
1 2 1 2

7
1 2 1 1 3 2 1

Sample Output

Case 1: 3

Case 2: 4

思路

这个刚开始想确实一直不知道跟区间dp有什么关系。

这里有个决策上的问题就是你不知道当前遇到的派对你要脱掉旧的衣服还是穿上新的衣服

这个决策好像很难体现成状态转移方程，状态要怎么设一直想不出来。

我一直在想这个区间不会就只是前缀吧，好像也没有区间dp这样设状态的。一直被这个按顺序参加派对影响了，总觉得不可能先去算不是从开头开始的小区间。

这作为一道区间dp状态当然就是 \(f[l][r]\) 表示区间 \(l\) 到 \(r\) 需要的最少衣服数。

难点就在与怎么维护穿上和脱下这些动作呢？（这个实在是想不到）

穿上衣服：

if(a[r-1]==a[r]) f[l][r]=f[l][r-1];
else f[l][r]=f[l][r-1]+1;

脱下衣服（当然是脱到可以参加这场派对的那一件）：

for(int k=l;k<r;k++)
{
	if(a[k]==a[r])
	{
		f[l][r]=min(f[l][r],f[l][k]+f[k+1][r-1]);
	}
}

这个脱下衣服是难想的以及难理解的点：

你找到了 \(l\) 到 \(r-1\) 区间的一个可以给你换的衣服 \(k\) 后，你把区间拆成两个区间 \((l,k)\) 和 \((k+1,r-1)\) ，当然 \((l,k-1)\) 和 \((k,r-1)\) 也可以。

意思就是你在前一个区间结束的时候你穿的是 \(k\) ，然后到后一个区间结束的时候你把这后一个区间穿上的衣服全脱掉，这后一个区间的衣服全都是新穿上去的（这区间内的派对都没有用到前面的衣服），我们的状态其实也是设没有用到其他区间的衣服，这就确保了无后效性。

#include <bits/stdc++.h>
using namespace std;
int a[110];
int n;
int f[110][110];
int dfs(int l, int r)
{
    if (~f[l][r])
        return f[l][r];
    if(l>r)
        return 0;
    if (l == r)
        return f[l][r] = 1;
    int res = 110;
    if(a[r]!=a[r-1])
        res = dfs(l, r - 1) + 1;
    else
        res = dfs(l, r - 1);
    for (int k = l ; k < r; k++)
    {
        if(a[k]==a[r])
        {
            res = min(res, dfs(l, k) + dfs(k + 1, r - 1));
        }
    }
    return f[l][r] = res;
}
int main()
{
    int t;
    cin >> t;
    int cas = 0;
    while (t--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        for (int i = 1; i <= n; i++)
            for (int j = i; j <= n; j++)
                f[i][j] = -1;
        cout <<"Case "<<++cas<<':'<<' '<< dfs(1, n) << endl;
    }
}