You just inherited the rights to N (1 <= N <= 20) previously unreleased songs recorded by the popular group Raucous Rockers. You plan to release a set of M (1 <= M <= 20) compact disks with a selection of these songs. Each disk can hold a maximum of T (1 <= T <= 20) minutes of music, and a song can not overlap from one disk to another.
你刚刚获得了流行乐队Raucous Rockers录制的N（1 <= N <= 20）首未发行歌曲的版权。您计划发布一组M（1 <= M <= 20）张包含这些歌曲的 CD。每张 CD 可以保存最多T（1 <= T <= 20）分钟的音乐，并且一首歌曲不能分段保存。
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 on the set of disks must appear in the order of the dates that they were written.
- The total number of songs included will be maximized.
由于你是古典音乐迷，无法判断这些歌曲的艺术价值，你决定根据以下标准进行选择：
- CD 上的歌曲必须按照这些歌曲的完成时间依次出现（从较早到较晚）。
- 最大化包含的歌曲总数。
PROGRAM NAME: rockers
INPUT FORMAT 输入格式
Line 1: Three Integers: N, T, and M.
Line 2: N integers that are the lengths of the songs ordered by the date they were written.
第 1 行：三个整数 N，T和M。
第 2 行：N 个整数，表示了每首歌曲的长度（按照完成时间排序）。
SAMPLE INPUT (file rockers.in) 样例输入（文件 rockers.in)
4 5 24 3 4 2
OUTPUT FORMAT 输出格式
A single line with an integer that is the number of songs that will fit on M disks.
SAMPLE OUTPUT (file rockers.out) 样例输出（文件 rockers.out）
3
题解
类似背包；上代码：
1 /* 2 ID: hanghan1 3 LANG: C++11 4 PROB: rockers 5 */ 6 #define _TASK_ "rockers" 7 #include8 using namespace std; 9 #define N 10510 int dp[N][N], len[N], f[N];11 12 int main() {13 freopen(_TASK_ ".in", "r", stdin);14 freopen(_TASK_ ".out", "w", stdout);15 int n, t, m; scanf("%d%d%d", &n,&t,&m);16 for (int i=1; i<=n; i++) scanf("%d", &len[i]);17 for (int i=1; i<=n; i++) {18 for (int j=m; j>=1; j--) {19 dp[j][0] = f[j-1];20 for (int k=t; k>=len[i]; k--) if (dp[j][k] < dp[j][k-len[i]]+1) {21 dp[j][k] = dp[j][k-len[i]]+1;22 f[j] = max(f[j], dp[j][k]);23 }24 }25 }26 printf("%d\n", f[m]);27 return 0;28 }