uva473
Raucous Rockers |
You just inherited the rights to n previously unreleased songs recorded by the popular group Raucous Rockers. You plan to release a set of m compact disks with a selection of these songs. Each disk can hold a maximum of t minutes of music, and a song can not overlap from one disk to another. Since you are a classical music fan and have no way to judge the artistic merits of these songs, you decide on the following criteria for making the selection:
- The songs will be recorded on the set of disks in the order of the dates they were written.
- The total number of songs included will be maximized.
Input
The input consists of several datasets. The first line of the input indicates the number of datasets, then there is a blank line and the datasets separated by a blank line. Each dataset consists of a line containing the values of n, t and m (integer numbers) followed by a line containing a list of the length of n songs, ordered by the date they were written (Each is between 1 and t minutes long, both inclusive, and .)
Output
The output for each dataset consists of one integer indicating the number of songs that, following the above selection criteria will fit on m disks. Print a blank line between consecutive datasets.
Sample Input
2 10 5 3
3, 5, 1, 2, 3, 5, 4, 1, 1, 5 1 1 1
1
Sample Output
6 1
这题说的是给了 一个序列的的歌曲播放的时间分别是t0---tn-1 然后 有m个磁盘 每个磁盘可以存T分钟的歌曲,不能有一首歌放在两个磁盘或者以上,求m个磁盘所能容下的最多歌曲的个数
dp[i][j][k] 表示 第i首歌放在j的磁盘k位置的最大值 , 当他放在第一个位置时需要特判一下从上一个磁盘的末尾得到,否者对每个磁盘采用01背包,由于数据大采用滚动数组
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn=;
int dp[maxn][maxn];
int t[maxn],n,T,m;
int main()
{
int cas;
scanf("%d",&cas);
for(int cc = ;cc<=cas; ++cc){
scanf("%d%d%d",&n,&T,&m);
memset(dp,,sizeof(dp));
for(int i=; i<n; ++i){
int d;
scanf("%d%*c",&d);
for(int j=m; j>=; j--)
for(int k=T; k>=d; --k){
dp[j][k]=max(dp[j][k],dp[j-][T]+);
dp[j][k]=max(dp[j][k],dp[j][k-d]+);
}
}
if(cc==cas) printf("%d\n",dp[m][T]);
else printf("%d\n\n",dp[m][T]);
}
return ;
}
最新文章
- angularjs+微信,解决chooseImage不能预览的问题
- php 无限极
- 分享一个简单程序(webApi+castle+Automapper+Ef+angular)
- YARN的内存和CPU配置
- A simple visualization of energy function and energy gap in hopfield nets
- Python开发的10个小贴士
- SqlServer 三级联动、递归表
- 本篇文章主要是对jquery+ajax+C#实现无刷新操作数据库数据的简单实例进行了介绍,需要的朋友可以过来参考下,希望对大家有所帮助
- java面试题集1
- HTML5新增的主体元素和新增的非主体结构元素
- HDU2094(产生冠军)题解
- .net EF 事物 订单流水号的生成 (二):观察者模式、事物、EF
- 向openwrt 源码添加ap143支持
- Python的多线程编程
- MongoDB安装篇-Win7 X64
- 【java】字节码操作技术
- zabbix3.2使用fping批量监控ip的连通性
- 树莓派播放网络磁盘MP3文件
- 关于IOS下click事件委托失效的解决方案
- android控制软键盘弹出方式