LightOJ 1422 Halloween Costumes
传送门：http://vjudge.net/contest/77874#problem/B
题目翻译
一个人，按顺序参加N个派对，不同的派对需要不同的服装。衣服可以新买穿/脱/套着，问至少需要新买多少件衣服。
题解
F[left][right] 表示 从第 left 天到第 right 天需要新买多少件衣服。
首先如果什么都不考虑，F[left][right]=F[left+1][right]+1
然后考虑穿相同衣服的情况，如果存在一天 K ,使 left 与 K 穿的服装相同，我们尝试在left天把衣服穿在里面不脱，等到第 K 天再使用 。 F[left][right] = min ( F[left+1][K] + F[K+1][Right] , F[left][right] )
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include<cstring> #include<cstdlib> #include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int Maxn=100; int n; int num[Maxn+5]; int F[Maxn+5][Maxn+5]; inline void solve(int T){ scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&num[i]); memset(F,0,sizeof(F)); for (int left=1;left<=n;left++) for (int right=left;right<=n;right++) F[left][right]=right-left+1; for (int left=n;left>=1;left--){ for (int right=left+1;right<=n;right++){ F[left][right]=F[left+1][right]+1; for (int k=left+1;k<=right;k++) if (num[left]==num[k]) F[left][right] = min(F[left][right],F[left+1][k-1]+F[k][right]); } } printf("Case %d: %d\n",T,F[1][n]); } int main(){ int T=0; while(scanf("%d",&T)!=EOF){ for (int i=1;i<=T;i++) solve(i); } return 0; } |
原文链接：LightOJ 1422 Halloween Costumes
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!