区间DP
N个party 最少需要多少件衣服
最坏的情况肯定是 需要N件
按题意 如果 是 1 2 1
那么第一场穿1 第二场在1的基础上穿2 第三场脱掉2 那么就只需要2件就可以了
DP[i][j]表示从i 到j需要多少件衣服 有俩种情况, 第一种就是在i -> j - 1 中没有与j 要求穿的衣服想同的 那么就在dp[i][j-1]的基础上多加一件
还有一种就是 i -> j-1 有与j相同衣服的
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define INF 999999 typedef long long ll; int const MAXN = 110; int dp[MAXN][MAXN],c[MAXN]; inline int Min(int a,int b){ return a<b?a:b; } int main(){ int t; while(~scanf("%d",&t)){ for(int cnt = 1;cnt <= t;cnt++){ int n; scanf("%d",&n); for(int i = 1;i <= n;i++){ scanf("%d",&c[i]); } memset(dp,0,sizeof(dp)); for(int i = 1;i <= n;i++){ for(int j = i;j <= n;j++){ dp[i][j] = j - i + 1; } } for(int l = 2;l <= n;l++){ for(int i = 1;i <= n - l + 1;i++){ int j = i + l - 1; dp[i][j] = Min(dp[i][j],dp[i][j - 1] + 1); for(int k = i;k < j;k++){ if(c[k] == c[j]){ dp[i][j] = Min(dp[i][j],dp[i][k - 1] + dp[k + 1][j]); } } //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl; } } printf("Case %d: %d\n",cnt,dp[1][n]); } } return 0; }