Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

解题报告

Posted by hzoi2017_zyc at 2018-05-13 17:13:41 on Problem 2228
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator