tkdsheep-solution-0030

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
个人觉得这是一道非常不错的DP题，题目描述看起来很大自然，读懂之后觉得是大水题，实际写的时候又被无数坑。。可惜比赛的时候大家都没做这题

题意？有一个人，他生物钟很规律，睡醒之后必须等恰好T秒才能继续入睡，每次睡觉都是睡X秒
但是超过T秒还不睡觉，就等于在熬夜，熬夜最多可以熬L秒，也就是到了T+L秒的时候，会强制入睡。。。
并且睡眠时间会在X的基础上再加熬夜的那部分时间（俗称“补睡眠”）


然后现在有许多比赛，比如CF、TC，它们都有一个开始时间和结束时间，要做比赛就必须从开始到结束全程做，不能提前开始和迟到、早退
每个比赛有一个value值，现在要求怎样安排睡眠和醒着的时候做哪些比赛，使总的value最高

另外还有一个非常有趣的条件，是本题的亮点，就是当我熬夜做比赛的时候，比如我熬夜熬了y秒才睡觉，那么我实际得到的总value值会减掉一个y*y（注意是y的平方）
这个条件使得后面的dp转移非常容易写错

dp是怎么来的？因为数据范围适合DP，比赛最多1000场，所有比赛的结束时间不会超过10000，T不会超过100，L不会超过20，也就是说我最多醒120秒就必须入睡

所以可以得出一个10000*120的dp，即dp[i][j]表示当前时间为第i秒，我已经醒了j秒，当前得到的总value最大是多少？

对于dp[i][j]这个状态，我有3种选择：

1.如果j<T+L,那么我可以继续醒着，什么都不做，用dp[i][j]去更新dp[i+1][j+1]，但是这里要注意一个问题！如果j>=T了，那么j+1就是在熬夜！
  熬夜的话多熬了1秒，就会对value造成损失，所以应该用dp[i][j]加上一个suffer值来更新dp[i+1][j+1],这个suffer应该等于多少？大家可以自己想想，我都已经把坑揭开了
2.如果j>=T，那么我可以选择去睡觉，用dp[i][j]去更新dp[i+sleep][0]，这个sleep代表我睡觉所花的时间，sleep等于多少？根据题目条件去计算
3.如果时刻i有比赛开始，那么我可以选择去做这个比赛，但必须保证做完这场比赛之后，j+len<=L+T，len表示比赛的长度，否则我就会在比赛中途睡着。。
  而这个转移更第1种情况一样，要考虑那个suffer值，大家可以自己想一下

最后ans就是所有dp[i][j]中的最大值
}}}

个人觉得这是一道非常不错的DP题，题目描述看起来很大自然，读懂之后觉得是大水题，实际写的时候又被无数坑。。可惜比赛的时候大家都没做这题
题意？有一个人，他生物钟很规律，睡醒之后必须等恰好T秒才能继续入睡，每次睡觉都是睡X秒
但是超过T秒还不睡觉，就等于在熬夜，熬夜最多可以熬L秒，也就是到了T+L秒的时候，会强制入睡。。。
并且睡眠时间会在X的基础上再加熬夜的那部分时间（俗称“补睡眠”）
然后现在有许多比赛，比如CF、TC，它们都有一个开始时间和结束时间，要做比赛就必须从开始到结束全程做，不能提前开始和迟到、早退
每个比赛有一个value值，现在要求怎样安排睡眠和醒着的时候做哪些比赛，使总的value最高
另外还有一个非常有趣的条件，是本题的亮点，就是当我熬夜做比赛的时候，比如我熬夜熬了y秒才睡觉，那么我实际得到的总value值会减掉一个y*y（注意是y的平方）
这个条件使得后面的dp转移非常容易写错
dp是怎么来的？因为数据范围适合DP，比赛最多1000场，所有比赛的结束时间不会超过10000，T不会超过100，L不会超过20，也就是说我最多醒120秒就必须入睡
所以可以得出一个10000*120的dp，即dp[i][j]表示当前时间为第i秒，我已经醒了j秒，当前得到的总value最大是多少？
对于dp[i][j]这个状态，我有3种选择：
1.如果j<T+L,那么我可以继续醒着，什么都不做，用dp[i][j]去更新dp[i+1][j+1]，但是这里要注意一个问题！如果j>=T了，那么j+1就是在熬夜！
  熬夜的话多熬了1秒，就会对value造成损失，所以应该用dp[i][j]加上一个suffer值来更新dp[i+1][j+1],这个suffer应该等于多少？大家可以自己想想，我都已经把坑揭开了
2.如果j>=T，那么我可以选择去睡觉，用dp[i][j]去更新dp[i+sleep][0]，这个sleep代表我睡觉所花的时间，sleep等于多少？根据题目条件去计算
3.如果时刻i有比赛开始，那么我可以选择去做这个比赛，但必须保证做完这场比赛之后，j+len<=L+T，len表示比赛的长度，否则我就会在比赛中途睡着。。
  而这个转移更第1种情况一样，要考虑那个suffer值，大家可以自己想一下
最后ans就是所有dp[i][j]中的最大值