加载中…HDU 3905 Sleeping 2011 Multi-University Training Contest 7 - Host by ECNU
(2011-08-02 21:56:37)
标签：
hdu3905sleepingit |
分类： 动态规划 |
题目描述：
上课，一共有n分钟，需要睡觉m分钟（不要求连续），每分钟都有一个权值。如果连续听课大于等于L分钟，就能获得这个连续区间的权值。
问，能获得最大权值是多少。
解题报告：
dp[i][j] 表示第i分钟已经睡觉j分钟时，能获得最大权值。
首先，第i分钟可以睡觉，那么dp[i][j] = dp[i - 1][j - 1];
也可以不睡觉，听课，对于每个k( 0 <= k <= i - l)，求的dp[k][j] + sum[i] - sum[k]的最大值，就是当前的权值。而这个取最大的操作，可以用一个数组保存起来，随时更新，不需要额外的复杂度。
其中，sum[i]表示前i分钟权值的总和。
代码很短，如下：
while(scanf("%d%d%d", &n,
&m, &l) != EOF)
{
for(int i = 1; i
<= n; i++) scanf("%d", &x[i]);
sum[0] = 0;
memset(jeo, 0,
sizeof(jeo));
for(int i = 1; i
<= n; i++)
sum[i] = sum[i - 1] + x[i];
memset(dp, 0,
sizeof(dp));
int ans = -1;
for(int i = 1; i
<= n; i++)
for(int j = 0; j <= m
&& j <= i;
j++)
{
dp[i][j] =
dp[i - 1][j];
if (j > 0) dp[i][j] =max(dp[i -
1][j], dp[i - 1][j - 1]);
if (i - l
>= 0 && i - l
>= j)
jeo[j] = max(jeo[j] + x[i],
dp[i - l][j] + sum[i] - sum[i - l]);
if (i - l
>= 0) dp[i][j] = max(dp[i][j], jeo[j]);
if (j == m
&& dp[i][j] > ans)
ans = dp[i][j];
}
printf("%d\n", ans);
}
上课，一共有n分钟，需要睡觉m分钟（不要求连续），每分钟都有一个权值。如果连续听课大于等于L分钟，就能获得这个连续区间的权值。
问，能获得最大权值是多少。
解题报告：
dp[i][j] 表示第i分钟已经睡觉j分钟时，能获得最大权值。
首先，第i分钟可以睡觉，那么dp[i][j] = dp[i - 1][j - 1];
也可以不睡觉，听课，对于每个k( 0 <= k <= i - l)，求的dp[k][j] + sum[i] - sum[k]的最大值，就是当前的权值。而这个取最大的操作，可以用一个数组保存起来，随时更新，不需要额外的复杂度。
其中，sum[i]表示前i分钟权值的总和。
代码很短，如下：
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
int n, m, l, dp[2000][2000], x[2000], sum[2000],
jeo[2000];
int main()
{
if (j > 0) dp[i][j] =
return 0;
}
喜欢
0
赠金笔