UVA12283 Halloween Costumes 题解

Light_Star_RPmax_AFO · 2023-07-23 15:28:59 · 题解

题目描述

Gappu 有 n 次派对和 m 种服装，每次派对需要第 a_i 种衣服，如果想要已经穿在身上的第 i 件衣服，那么就需要脱掉所有套在 i 外面的 j。而且脱掉后的衣服 Gappu 是不会再穿的，问最少需要几件衣服才能让 Gappu 度过所有的舞会。

思路

区间 dp。

固定 i < j，i 和 j 都表示当前派对所需要的衣服。

设 dp_{i,j} 表示在 [i,j] 中所需要的衣服件数。

1. 如果 i 和 j 的衣服一样，在 [i,j] 之间所消耗的衣服应该是 [i,j - 1]，因为我们可以先套上 j - i 件衣服之后再脱掉就可以得到 i，满足了 j，dp_{i,j} = \min(dp_{i,j-1})。

2. 如果 i 和 j 不一样那么 dp_{i,j} = \min(dp_{i,j - 1} + 1)。

3. 如果要满足 [i,j] 可以先满足 [i,k] 和 [k+1,j] 也就满足了 [i,j] 所以 dp_{i,j} = \min(dp_{i,k} + dp_{k + 1,j}(i\le k< j))

AC Code

#include<bits/stdc++.h>
#define ll long long
#define Fup(i,j,k) for(int i = j;i <= k;++i)
#define Fdn(i,j,k) for(int i = j;i >= k;--i)
using namespace std;

inline int read()
{
    int x = 0,f = 1;char ch = getchar();
    while (ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while (ch >= '0' && ch <= '9'){x = x * 10 + ch - 48;ch = getchar();}
    return x * f;
}

void write(int x)
{
    if(x < 0)
       putchar('-'),x =- x;
    if(x > 9)
       write(x / 10);
    putchar(x % 10 + '0');
    return;
}

int n,a[110],m,dp[110][110];

int main(){
    int T = read();
    Fup(cnt,1,T){
        n = read(),m = read();
        for(int i = 1;i <= n;i++){
            a[i] = read();
        }
        for(int len = 1;len <= n;len++){
            for(int i = 1;i <= n - len + 1;i++){
                int j = i + len - 1;
                if(i == j){
                    dp[i][j] = 1;
                    continue;
                }
                if(a[i] == a[j])
                    dp[i][j] = dp[i][j - 1];
                else 
                    dp[i][j] = dp[i][j - 1] + 1;
                for(int k = i;k < j;k++){
                    dp[i][j] = min(dp[i][j],dp[i][k] + dp[k + 1][j]);
                }
            }
        }
        printf("Case %d: %d\n",cnt,dp[1][n]);
    }

    return 0;
}