【bzoj1737】[Usaco2005 jan]Naptime 午睡时间 dp
题目描述
Goneril is a very sleep-deprived cow. Her day is partitioned into N (3 <= N <= 3,830) equal time periods but she can spend only B (2 <= B < N) not necessarily contiguous periods in bed. Due to her bovine hormone levels, each period has its own utility U_i (0 <= U_i <= 200,000), which is the amount of rest derived from sleeping during that period. These utility values are fixed and are independent of what Goneril chooses to do, including when she decides to be in bed. With the help of her alarm clock, she can choose exactly which periods to spend in bed and which periods to spend doing more critical items such as writing papers or watching baseball. However, she can only get in or out of bed on the boundaries of a period. She wants to choose her sleeping periods to maximize the sum of the utilities over the periods during which she is in bed. Unfortunately, every time she climbs in bed, she has to spend the first period falling asleep and gets no sleep utility from that period. The periods wrap around in a circle; if Goneril spends both periods N and 1 in bed, then she does get sleep utility out of period 1. What is the maximum total sleep utility Goneril can achieve?
输入
* Line 1: Two space-separated integers: N and B
* Lines 2..N+1: Line i+1 contains a single integer, U_i, between 0 and 200,000 inclusive
输出
* Line 1: A single integer, the maximum total sleep utility Goneril can achieve.
样例输入
5 3
2
0
3
1
4
样例输出
6
题解
dp
先不管环的问题,想象成一个时间段。
那么很容易想到状态转移方程:
f[i][j]=max(f[i-1][j-1]+w[i],g[i-1][j-1])
g[i][j]=max(f[i-1][j],g[i-1][j])
其中f[i][j]表示前i个小时中总共睡j个小时,且其i个小时睡的最大效用值,
g[i][j]表示前i个小时中总共睡j个小时,且其i个小时不睡的最大效用值。
答案就是max(f[n][b],g[n][b])。
然后考虑环的问题。
除了刚才讨论的情况之外,如果出现环,一定是从某个点开始,经过n和1,再停止。
这时候n和1一定是睡的情况。
考虑断环,那么和正常情况相比,唯一的区别就是从1开始的一段中,w[1]也算进了答案中(题目中描述:每一段的第一段都不算进效用值)。
所以改一下初始条件,再按照同样的方法跑一遍dp即可,答案是f[n][b]。
最后取最大值即可。
由于空间限制,需要使用滚动数组黑科技,看代码应该不难理解。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int f[2][3831] , g[2][3831] , w[3831];
int main()
{
int n , b , i , j , ans = 0x80808080;
scanf("%d%d" , &n , &b);
for(i = 1 ; i <= n ; i ++ )
scanf("%d" , &w[i]);
memset(f , 0x80 , sizeof(f));
memset(g , 0x80 , sizeof(g));
f[1][1] = g[1][0] = 0;
for(i = 2 ; i <= n ; i ++ )
{
for(j = 0 ; j <= b ; j ++ )
{
if(j)
f[i & 1][j] = max(f[(i & 1) ^ 1][j - 1] + w[i] , g[(i & 1) ^ 1][j - 1]);
g[i & 1][j] = max(f[(i & 1) ^ 1][j] , g[(i & 1) ^ 1][j]);
}
}
ans = max(f[n & 1][b] , g[n & 1][b]);
memset(f , 0x80 , sizeof(f));
memset(g , 0x80 , sizeof(g));
f[1][1] = w[1];
for(i = 2 ; i <= n ; i ++ )
{
for(j = 0 ; j <= b ; j ++ )
{
if(j)
f[i & 1][j] = max(f[(i & 1) ^ 1][j - 1] + w[i] , g[(i & 1) ^ 1][j - 1]);
g[i & 1][j] = max(f[(i & 1) ^ 1][j] , g[(i & 1) ^ 1][j]);
}
}
ans = max(ans , f[n & 1][b]);
printf("%d\n" , ans);
return 0;
}
最新文章
- fzuoj Problem 2129 子序列个数
- hdu 3487 Play with Chain
- mac配置svn服务器
- MVC-起始页面设置
- Java 加密 AES 对称加密算法
- usaco 奶牛接力
- zsh中home键失灵问题
- BeanUtils复制属性
- C#开发微信公众号-学习笔记
- C++Builder中MessageBox的基本用法
- [bzoj2648/2716]SJY摆棋子
- 安装Emacs并设置racket环境
- A11-java学习-二维数组-面向对象概念-类的编写-测试类的编写-创建对象-使用对象-递归
- php中的接口interface
- win10定时执行php脚本
- Oracle 12C -- clone a remote pdb
- 洛谷P2018消息传递
- 【[POI2010]ANT-Antisymmetry】
- CentOS系统yum源配置修改、yum安装软件包源码包出错解决办法apt.sw.be couldn&#39;t connect to host
- js 动态创建变量