日志
【题解】睡觉
|
问题描述：
为了提高程序解题能力，勤奋努力的QQ天天锯题到深夜，导致睡眠严重不足，可NOIP决赛就要来临了，必须要有良好的状态才行啊，因此QQ决定准备拿出一天时间，好好补补觉。
他把这一天等分成了n个时间段，在每个时间段睡觉能获得精神点数不尽相同，在第i段时间能获得V[i]的精神点数。
由于勤奋的QQ觉得整天都睡太堕落了，他决定最多只能睡m个时间段。至于其他的时间吗...那自然是勤奋地锯题...
有两点事情要特别提出注意：
1.QQ不可能一上床马上睡着，他在连续一段睡觉时间的第一个时间段不能获得此时的V。也就是说如果他在i...j中的所有时间都休息了，获得的精神点数为V[i+1]+...+V[j]。
2.所有的时间段呈环形分布，也就是说第n个时间段之后为第1个时间段。
要求的自然是QQ最多能获得的精神点数之和。
输入格式：
第一行两个正整数n,m，意义如题所述
接下来n行，每行一个非负整数V[i]
输出格式：
一行，表示QQ最多能获得的精神点数之和
输入样例：
5 3
2
0
3
1
4
输出样例：
6
样例解释：
选择4、5、1三个时间段休息，在5、1时睡着，最大值为4+2=6
数据范围：
对于20%的数据n<=20
对于50%的数据n<=200
对于100%的数据n<=5000,m<=n,V[i]<=10000 这又是一道DP很容易看出，而且很容易联想到一些做过的模型。。。当时做的时候第一反应就想到了抄书那题的方程，不过那个题是3方的DP过不完这个题的数据而且有些细节没有处理好，过了样例就交了结果果断WA完了。。。
实际上此题是一个空间和时间都是2方的DP，方程也不是很难想，主要是被第一印象迷惑所以没弄出来，直接说下方程吧
f[i,j,0]表示前i个时间点一共睡了j个并且第i个没有睡，f[i,j,1]表示前i个时间点一共睡了j个而且第i个时间点睡了的，转移也很方便
f[i,j,0]:=max(f[i-1,j,0],f[i-1,j,1]);f[i,j,1]:=max(f[i-1,j-1,0],f[i-1,j-1,1]+v[i]);
不过这样是过不了样例的，因为题中还说了环这种情况，那么怎么处理环呢，如果用加倍的方法进行n次dp那么超时必然，所以这个题不能这么处理，那么如何做呢，其实我们可以分析一下有环的情况和没环时本质区别：在于第一个时间点和最后一个时间点是不是连续睡了，如果是的话那相当于环，如果没有那就不是环，因此只有3种情况：第一次没有睡，不是环，所以初值有f[1,1,0]:=0;f[1,1,1]:=-max,之后DP一次；从第一次开始睡，也不是环，f[1,1,1]:=0;f[1,1,0]:=-max,再DP一次;第一次睡了而且不是从第一次开始的，这是环的情况，所以f[1,1,0]:=-max;f[1,1,1]:=v[1],之后DP一次。
值得注意的是前2种情况最优解在f[n,m,0]和f[n,m,1]中取而环的时候最优解只能是f[n,m,1]否则不能构成环。。接下来代码就简单了。不过要用到01滚动，此题空间128m伤不起。。
全部作者的其他最新日志
- • 【OCG回忆录】（四）
- • 【OCG回忆录】（三）
- • 【OCG回忆录】（二）
- • 【OCG回忆录】（一）
