f[i][j][k] 从前i首歌中选, 放入前j张碟, 每张蝶时间为k 的歌曲数量.
/**//*
ID: lorelei3
TASK: rockers
LANG: C++
*/
#include <fstream>
using namespace std;
const int MAX = 25;
int f[MAX][MAX][MAX];
int cost[MAX];
int N,T,M;
inline int max(int a, int b)
{
return a>b? a: b;
}
int main(){
int i,j,k;
ifstream fin("rockers.in");
ofstream fout("rockers.out");
fin>>N>>T>>M;
for(i=1; i<=N; ++i)
fin>>cost[i];
for(i=1; i<=N; ++i)
for(j=1; j<=M; ++j)
for(k=1; k<=T; ++k)
if(k<cost[i])
f[i][j][k] = max(f[i-1][j][k], f[i-1][j-1][T]); // 如果不选, 就取要这k分钟+以前的专辑的最优值 或 以前的专辑的最优值
else
f[i][j][k] = max(f[i-1][j][k-cost[i]], f[i-1][j-1][T])+1; //取这首歌 取以前专辑的最优值+1 或 取当前专辑的最优值+1
fout<<f[N][M][T]<<endl;
return 0;
}posted on 2011-01-20 17:22
小阮 阅读(425)
评论(0) 编辑 收藏 引用 所属分类:
USACO