Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
解题报告O(n^2)环形DP 大意: 一天n小时,牛要睡觉恢复体力,不同的时间点恢复不同的精力 一天内可以睡任意次,持续任意长时间 但每次睡眠的第一小时都不能恢复精力 求一天睡p小时最多恢复多少精力 注意: 时间是连续的,明显的环形DP 分析: 对于环形DP,我们可以进行两次DP 对于每天的第一小时,无非两类状况 一类是醒着或入睡,这两种情况均与昨天无关,故分为一组 另一类是陷入睡眠,这类情况下,一天的最后一小时至少是要入睡 因此状态就容易得到了 dp[i][j][0]表示在这一天的第i个小时,牛已经休息了j个小时,并且第i个小时没有休息 与之相对的 dp[i][j][0]表示在这一天的第i个小时,牛已经休息了j个小时,并且第i个小时正在休息, 可以刚入睡,也可以陷入睡眠 两类要分别处理 边界: 第一类 dp[1][0][0]=dp[1][1][1]=0; 其余为负无穷 第二类 dp[1][1][1]=u[1]; 其余均为负无穷 状态转移: 两类均为 dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]); dp[i][j][1]=max(dp[i-1][j-1][0],dp[i-1][j-1][1]+u[i]); 千万注意! j的循环从0开始,注意转移中的数组越界! Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator