USACO Training Section 3.4 Raucous Rockers

英文原题 

大意：有S首歌，要放到D个CD里。每首歌有一个序号，每个CD有个序号，如果歌曲序号I放在CD（序号J）中，那么序号大于J的CD中不允许有序号小于I的歌曲。每个歌曲有个长度，CD可容纳的歌曲的长度相同并给定，每张CD中放的歌曲的总长度不能超过CD的容量T。求最多能放下多少首歌。

看看数据限制，S<=20, T<=20, D<=20，显然可以用简单的动态规划：best(s,t,d)表示序号s及之后的歌曲要放入最后d张CD中，其中序号最大的CD剩余的容量为t，其余CD剩余容量为T（初始容量）。那么，只有三种可能情况：
1.放弃歌曲s，那么s不能出现在之后的CD中，得best(s+1,t,d)；
2.如果歌曲s长度不超过本CD长度，则将其放入本CD中（显然如果要放这首歌，就不能放在后面的CD中），得best(s+1,t-len(s),d)+1；
3.如果将s放在这张CD中，可选择本CD中不再放其他歌曲，则得best(s+1,T,d-1)+1。
取这三种情况的最大值为best(s,t,d)，即为所求。

/*
ID: blackco3
TASK: rockers
LANG: C++
*/
#include <iostream>
#include <memory.h>
using namespace std;
const int _max_song_(20), _max_time_(20), _max_disc_(20) ;
int len[_max_song_], best[_max_song_+1][_max_time_+1][_max_disc_+1] ;

int main() {
	freopen("rockers.in", "r", stdin);
	freopen("rockers.out", "w", stdout);
	int n_song, time_limit, n_disc ;
	cin >> n_song >> time_limit >> n_disc ;
	for( int i=0; i<n_song; i++ )
		cin >> len[i] , best[i][0][0]=0;
	register int in , out ;
	memset( best, 0, sizeof(best) );
	for( int is=n_song-1; is>=0; is-- ){
		for( int it=0; it<=time_limit; it++ ){
			for( int id=1; id<=n_disc; id++ ){
				out = best[is+1][it][id] ;
				if( it>=len[is] )
					in = /*len[is]*/ 1 + max( best[is+1][it-len[is]][id], best[is+1][time_limit][id-1] );
				else 
					in = 0 ;
				best[is][it][id] = max( in, out ) ;
			}
		}
	}
	cout << best[0][time_limit][n_disc] << endl ;
	return 0 ;
}