[USACO3.4.4]rockers

Raucous Rockers

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.

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.

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.

SAMPLE INPUT (file rockers.in)

4 5 2 4 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)

3

题意就是：

给定n,T,M 然后n个歌曲的播放时间  要从中选出一些歌曲  使得各个歌曲的播放时间放到M个光盘 每个光盘的容量时间为T，注意

得一个一个放，一个光盘一个光盘放上去。

要求光盘不超过M个

可以暴力。 用DP[i,j]表示

处理前i个唱片，当前处理到第i个，第i个用了j分钟 

DP[i,0]表示前i-1个唱片，能够获得的最大歌曲  DP[i,j + x] = DP[i,j] + 1; 并更新 DP[i+1,0] = max(dp[i+1,0],dp[i,j + x]) 并更新 ANS  //如果能够放下  如果不能放下，那就算了，不放了  大家可以参考： 

http://train.usaco.org/usacoanal2?a=Q1IQssZeui7&S=rockers

DP[i,0]表示前i-1个唱片，能够获得的最大歌曲  DP[i,j + x] = DP[i,j] + 1; 并更新 DP[i+1,0] = max(dp[i+1,0],dp[i,j + x]) 并更新 ANS  //如果能够放下  如果不能放下，那就算了，不放了  大家可以参考： 

http://train.usaco.org/usacoanal2?a=Q1IQssZeui7&S=rockers

大家可以参考： http://train.usaco.org/usacoanal2?a=Q1IQssZeui7&S=rockers /* ID:cqz15311 LANG:C++ PROG:rockers */ #include<cstdio> #include<cmath> #include<algorithm> #include<cstdlib> #include<cstring> using namespace std; int N,T,M,ans,x,dp[26][26]; int main(){ freopen("rockers.in","r",stdin); freopen("rockers.out","w",stdout); scanf("%d%d%d",&N,&T,&M); memset(dp,-1,sizeof(dp)); dp[1][0] = 0; ans = 0; while (N--){ scanf("%d",&x); for (int i=M;i>=1;i--){ for (int j=T-x;j>=0;j--){ if ((dp[i][j] >= 0) && (dp[i][j+x] < dp[i][j] + 1)){ dp[i][j+x] = dp[i][j] + 1; if (dp[i][j+x]>dp[i+1][0]) dp[i+1][0]=dp[i][j+x]; if (dp[i][j+x]>ans) ans=dp[i][j+x]; } } }//防止重复 } printf("%d\n",ans); }