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:

1. The songs will be recorded on the set of disks in the order of the dates they were written.
2. 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

210 5 33, 5, 1, 2, 3, 5, 4, 1, 1, 51 1 11

Sample Output

61
这题说的是给了 一个序列的的歌曲播放的时间分别是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=105;int dp[maxn][maxn];int t[maxn],n,T,m;int main(){    int cas;    scanf("%d",&cas);    for(int cc =1 ;cc<=cas; ++cc){        scanf("%d%d%d",&n,&T,&m);         memset(dp,0,sizeof(dp));         for(int i=0; i<n; ++i){                int d;              scanf("%d%*c",&d);              for(int j=m; j>=1; j--)              for(int k=T; k>=d; --k){                 dp[j][k]=max(dp[j][k],dp[j-1][T]+1);                 dp[j][k]=max(dp[j][k],dp[j][k-d]+1);              }         }         if(cc==cas) printf("%d\n",dp[m][T]);         else printf("%d\n\n",dp[m][T]);     }    return 0;}

View Code

uva473