POJ2228 Naptime（环形结构上的dp）

灰太狼 2021-11-29 04:16 182阅读 0赞

## 题意：一天由n个小时构成，在第i个小时睡觉能够恢复Ui点体力。有一头牛要休息b个小时，可以不连续，但休息的第1个小时无法恢复体力。前一天的最后一个小时和第二天的第一个小时是连在一起的，求这头牛能恢复的体力最大值。 ##

## 分析：《算法竞赛进阶指南》P295-297。 ##

## 代码： ##

#include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <iostream>
    
    using namespace std;
    
    const int N = 4000, M = 4000;
    int n, m, f[2][M][2], w[N], ans;
    
    int main (){
    	scanf ("%d%d", &n, &m);
    	for (int i = 1; i <= n; i ++)
    		scanf ("%d", &w[i]);
    	if (m == 0)
    		 { printf ("0"); exit (0); }
    	memset (f, 0x80, sizeof f);
    	f[1 & 1][0][0] = 0;
    	f[1 & 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]);
    			if (j - 1 >= 0) f[i & 1][j][1] = max (f[(i - 1) & 1][j - 1][0], f[(i - 1) & 1][j - 1][1] + w[i]);
    		}
    	ans = max (f[n & 1][m][1], f[n & 1][m][0]);
    	memset (f, 0x80, sizeof f);
    	f[1 & 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]);
    			if (j - 1 >= 0) f[i & 1][j][1] = max (f[(i - 1) & 1][j - 1][0], f[(i - 1) & 1][j - 1][1] + w[i]);
    		}
    	ans = max (ans, f[n & 1][m][1]);
    	printf ("%d", ans);
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，182人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 2228 Naptime【环形DP】

某个星球上，一天由 N 个小时构成，我们称0点到1点为第1个小时、1点到2点为第2个小时，以此类推。在第 i 个小时睡觉能够恢复UiUi点体力。在这个星球上住着一...

ゝ一世哀愁。/ 2024年04月19日 10:55/ 0 赞/ 60 阅读

相关环形涂色（dp）

6. 环形涂色如上图，组成环形的格子需要涂3种颜色。它们的编号分别是1~14 相邻的格子不能用相同的颜色。涂色方案的数目是：24576 当格子数目

今天药忘吃喽~/ 2024年02月18日 19:18/ 0 赞/ 66 阅读

相关区间DP | 2：环上的合并石子 —— 例题：合并石子（环形）

本文是在[区间DP | 1：矩阵链乘问题（含优化） —— 例题：矩阵链乘、合并石子][DP _ 1_ _] 上的升级（建议先看链接文章）。从链到环的改变，但本质还是区间dp问题

傷城~/ 2023年07月17日 07:28/ 0 赞/ 33 阅读

相关 POJ 2228 Naptime 环形DP

参考 [https://blog.csdn.net/qq\_41925919/article/details/90267224][https_blog.csdn.net_q

「爱情、让人受尽委屈。」/ 2023年06月19日 02:16/ 0 赞/ 31 阅读

相关 1068 环形石子合并（环形区间dp变成链的技巧）

1. 问题描述：将 n 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。请编写一个程序，读

青旅半醒/ 2022年09月12日 12:56/ 0 赞/ 160 阅读

相关 POJ1163DP

题意和解析，看代码最后部分 include <iostream> include <cstdio> include <cmath> using

淡淡的烟草味﹌/ 2022年08月18日 00:40/ 0 赞/ 34 阅读

相关【POJ2228】Naptime

关于环形dp的处理，我采用的办法是，把整个问题分成两个问题。首先我们简化一下问题，假设这个问题不是环形的，那么我们定义f\[i\]\[j\]\[1\]表示前i个小时休息了j

一时失言乱红尘/ 2021年12月12日 09:07/ 0 赞/ 200 阅读

相关【dp】POJ-1050

从里面任意截取一个矩阵,使得矩阵所包含的数字的和最大. 首先考察该题的简化版：已知一列数，求任意连续若干个数和的最大值。因为是连续若干个自然数的和，那前面的某个数字取

淩亂°似流年/ 2021年12月05日 13:09/ 0 赞/ 264 阅读

相关 CH 5501 环路运输（环形结构上的dp）

题意：n个在一个环上的仓库，两两之间运货的代价是a\[i\]+a\[j\]+min(∣i−j∣,∣n−(i−j)∣) 求最大代价。分析：《算法竞赛进阶指南》P297。

àì夳堔傛蜴生んèń/ 2021年11月29日 04:24/ 0 赞/ 194 阅读

相关 POJ2228 Naptime（环形结构上的dp）

题意：一天由n个小时构成，在第i个小时睡觉能够恢复Ui点体力。有一头牛要休息b个小时，可以不连续，但休息的第1个小时无法恢复体力。前一天的最后一个小时和第二天的第一个小时是连

灰太狼/ 2021年11月29日 04:16/ 0 赞/ 183 阅读