艺术设计类网站,分类网站模板,建设假网站,免费电视剧大全网站288. 休息时间 - AcWing题库
在某个星球上#xff0c;一天由 N 个小时构成#xff0c;我们称 0 点到 1 点为第 1 个小时、1 点到 2 点为第 2 个小时#xff0c;以此类推。
在第 i 个小时睡觉能够恢复 Ui 点体力。
在这个星球上住着一头牛#xff0c;它每天要休息 B 个小…288. 休息时间 - AcWing题库
在某个星球上一天由 N 个小时构成我们称 0 点到 1 点为第 1 个小时、1 点到 2 点为第 2 个小时以此类推。
在第 i 个小时睡觉能够恢复 Ui 点体力。
在这个星球上住着一头牛它每天要休息 B 个小时。
它休息的这 B 个小时不一定连续可以分成若干段但是在每段的第一个小时它需要从清醒逐渐入睡不能恢复体力从下一个小时开始才能睡着。
为了身体健康这头牛希望遵循生物钟每天采用相同的睡觉计划。
另外因为时间是连续的即每一天的第 N 个小时和下一天的第 1 个小时是相连的N 点等于 0 点这头牛只需要在每 N 个小时内休息够 B 个小时就可以了。
请你帮忙给这头牛安排一个睡觉计划使它每天恢复的体力最多。
输入格式
第 1 行输入两个空格隔开的整数 N 和 B。
第 2..N1行第 i1行包含一个整数 Ui。
输出格式
输出一个整数表示恢复的体力值。
数据范围
3≤N≤3830 2≤BN 0≤Ui≤200000
输入样例
5 3
2
0
3
1
4输出样例
6样例解释
这头牛每天 3 点入睡睡到次日 1 点即[1,4,2] 时间段休息每天恢复体力值最大为 0426。
解析
DP的核心思想是用集合来表示一类方案然后从集合的维度来考虑状态之间的递推关系。
这里可以将集合划分为第 i 个小时睡与不睡
具体为f[i][j][1] 表示前 i 个小时睡了 j 个小时1 表示第 i 个小时睡了0 表示第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]w[i])
#includeiostream
#includecstdio
#includecstdlib
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemap
using namespace std;
typedef long long LL;
const int N 4e3, INF 0x3f3f3f3f;
int n, m;
int w[N];
int f[2][N][2];int main() {scanf(%d%d, n, m);for (int i 1; i n; i) {scanf(%d, w[i]);}memset(f, -0x3f, sizeof(f));f[1][0][0] f[1][1][1] 0;for (int i 2; i n; i) {for (int j 0; j m; j) {f[i 1][j][0] max(f[i - 1 1][j][0], f[i - 1 1][j][1]);f[i 1][j][1] -INF;if (j)f[i 1][j][1] max(f[i - 1 1][j - 1][0], f[i - 1 1][j - 1][1] w[i]);}}int ret f[n 1][m][0];memset(f, -0x3f, sizeof(f));f[1][0][0] 0, f[1][1][1] w[1];for (int i 2; i n; i) {for (int j 0; j m; j) {f[i 1][j][0] max(f[i - 1 1][j][0], f[i - 1 1][j][1]);f[i 1][j][1] -INF;if (j)f[i 1][j][1] max(f[i - 1 1][j - 1][0], f[i - 1 1][j - 1][1] w[i]);}}ret max(ret, f[n 1][m][1]);cout ret endl;return 0;
}
