LightOJ 1422 Halloween Costumes （区间DP）

￡神魔★判官ぃ 2023-06-04 13:58 7阅读 0赞

嗯...

题目链接：https://vjudge.net/problem/LightOJ-1422

题意：有n场派对，每场派对都有需要穿某套衣服去参加，可以同时穿多套衣服，就是一套套着一套，如果脱了的话就不能再穿上那套旧的了，问最少需要几套衣服去参加完所有派对。

设dp\[i\]\[j\]为第i场到第j场派对需要最少的衣服，则有dp\[i\]\[i\]=1。所以dp\[i\]\[j\]=min(dp\[i\]\[j-1\]+1,dp\[i\]\[k\]+dp\[k+1\]\[j-1\]) （i<=k<j，且第k场衣服与第j场相同）：

如果第j场另外穿一件就有dp\[i\]\[j\]=dp\[i\]\[j-1\]+1；否则就是第k场（i<=k<j，且第k场衣服与第j场相同）的衣服不脱下来一直到第j场，就有dp\[i\]\[j\]=dp\[i\]\[k\]+dp\[k+1\]\[j-1\]。

AC代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<iostream>
     3 
     4 using namespace std;
     5 
     6 int a[105], dp[105][105];
     7 
     8 int main(){
     9     int T;
    10     scanf("%d", &T);
    11     for(int t = 1; t <= T; t++){
    12         int n;
    13         scanf("%d", &n);
    14         for(int i = 1; i <= n; i++){ scanf("%d", &a[i]); dp[i][i] = 1;}
    15         for(int l = 1; l <= n; l++){
    16             for(int i = 1; i <= n; i++){
    17                 int j = i + l;
    18                 if(j > n) break;
    19                 dp[i][j] = dp[i][j - 1] + 1;
    20                 for(int k = i; k < j; k++){
    21                     if(a[k] == a[j]) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j - 1]);
    22                 }
    23             }
    24         }
    25         printf("Case %d: %d\n", t, dp[1][n]);
    26     }
    27     return 0;
    28 }

AC代码

转载于:https://www.cnblogs.com/New-ljx/p/11581325.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/bde085ac9e3941608b6cc42ef59de2d5.png