light oj 1422 – Halloween Costumes (区间dp)

light oj 1422 题目链接

题意:

按顺序去参加舞会。每个舞会对衣服都有要求。可以连续穿好多件衣服。需要时候就脱下来,但是一旦脱下来,这件衣服就报废了。问最少需要几件衣服。

 

思路:没有思路。我连这题是dp都看不出来。。知道是dp也一点思路都没。。虽然这道题是道区间dp的入门题。。。但是不怕被鄙视。。我一点也没思路。。

参考了10多篇题解。。。终于懂了一点。。

参考博客1
参考博客2
参考博客3
参考博客4

 

当a[i]和a[j]相等的时候    dp[i][j]=dp[i][j-1] 嗯,就这一个转移。然后就是区间dp的固定写法了。

这句话让我恍然大悟。。。难道。。都是套路?

 

dp[i][j]表示的是[i,j]之间最少需要的衣服数量。

初始化dp[i][i] = 1,表示每天都换一件新衣服,显然不优。

a[i]==a[j]时,dp[i][j] = dp[i][j-1] ,表示第j天不用新换衣服,

然后枚举划分区间的点k,分成[i,k]和[k+1,j]两部分,取所有情况中最好的(这大概就是区间dp的套路?)

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz