"无论何时何地都会遵守约定"。"奮力逃吧""关于取下敌人性命这件事,也从不失约"
小懒虫zmx平时最喜欢玩的游戏就是《王者荣耀31号几点更新》,在这款游戏中它也最喜欢百里守约这个英雄最近,zmx准备冲国服百里所以它开始练英雄,你有很多个时间段来练习英雄每个时间段有一个开始时间点和结束时間点,以及可以获得的熟练度不过现在你可以随意修改任意练习时间段的开始和结束时间点,但是你不能修改时间段的长度和获得的熟練度!由于要学习你只能在固定时间段玩游戏,问你最多可以获得多少熟练度
例如:你可以把[2,3),修改为[1,2)或者[3,4)等等他们的长度嘟是1。
注意:对于某个时间段不管你有没有修改,必须练完整个时间段长度才能获得熟练度!
输出一行包括一个整数,表示zmx能获得的朂大熟练度
可以看出,出这题的思路是把数值加法看做区间的覆盖,于是背包问题就可以变形成一个区间问题了
看出来之后就是一個裸的01背包,背包的大小为T-S
第 i 个时间段可以看成一个物品,这个物品的体积w[i]=b[i]-a[i]价值v[i] 为熟练度c。
那么dp[i][j]就表示着在前 i 个时间段里花费 j 的时间練英雄能得到的最大熟练度