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] )

代码