# 劲歌金曲

【题目链接】劲歌金曲

【题目类型】01背包

&题解：

题意：求在给定时间内，最多能唱多少歌曲，在最多歌曲的情况下，使唱的时间最长。
该题类似于01背包问题，可用01背包问题的解题思路来求，每个歌曲相当于物品，歌曲的长度相等于物品重量，每个歌曲的“价值”为1。由于金歌劲曲时间最长，所以最后要留至少1秒时间开始唱金歌劲曲，所以计算t-1时间内最多唱的歌曲和时间，最终答案为歌曲数加1，时间加上金歌劲曲的时间。这里我使用滚动数组计算这个值， 用len记录t-1。
需要注意的是，由于要求是连续唱歌，且要求在最多歌曲数的情况下时间最长，如果按普通的背包存储，很难得到最长时间，因为f[len] 只存储了最多的歌曲数，但并不知道这些歌曲到底唱了多少时间。假设最多歌曲数为num, 唱num首歌曲最少时间为tmin, 那么数组中从f[tmin]到f[len]都等于num,我们无法得知唱num首歌的最大时间。比如说len = 10, t[1] = 5, t[2] = 8, 那么f[5] 到 f[10] 都等于1， 无法知道唱从5到10哪个是唱1首歌的最长时间。如何处理呢？
这里需要用到一个技巧：对决策进行一定的限定！ 在计算某个时间最多唱的歌曲时，必须是该时间内恰好唱完这些歌，时间多了不行。即f[j]表示的是在j 的时间恰好用完的情况下最多能唱多少首歌。比如上面的例子只有f[5] 和f[8]等于1，其他的都等于0。这样的话处理时先算出最多唱的歌曲数 num，然后从j = len开始遍历数组f, 第一个等于num的就是在最多歌曲情况下的最长时间。
参考于：http://blog.csdn.net/yanzheshi/article/details/47086461

这是01背包的变形，但上面的想法确实很巧妙，也就是巧妙在定义f数组所表示的状态的时候，真的应该学习下这种分析问题的过程。
【时间复杂度】O(n*10000)

&代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;

#define cle(a,val) memset(a,(val),sizeof(a))

#define SI(N) scanf("%d",&(N))

#define SII(N,M) scanf("%d %d",&(N),&(M))

#define SIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))

#define rep(i,b) for(int i=0;i<(b);i++)

#define rez(i,a,b) for(int i=(a);i<=(b);i++)

#define red(i,a,b) for(int i=(a);i>=(b);i--)

const ll LINF = 0x3f3f3f3f3f3f3f3f;

#define PU(x) puts(#x);

#define PI(A) cout<<(A)<<endl;

#define DG(x) cout<<#x<<"="<<(x)<<endl;

#define DGG(x,y) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<endl;

#define DGGG(x,y,z) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<" "<<#z<<"="<<(z)<<endl;

#define PIar(a,n) rep(i,n)cout<<a[i]<<" ";cout<<endl;

#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<" ";cout<<endl;}

const double EPS = 1e-9 ;

/*  ////////////////////////   C o d i n g  S p a c e   ////////////////////////  */

const int MAXN = 10000 + 9 ;

int K,n,t,a,f[MAXN];

void Solve()

{

    cle(f,0);

    int ma=0;

    SII(n,t); t--;

    rep(i,n){

        SI(a);

        red(j,t,a){

            if (f[j-a]||j==a){

                f[j]=max(f[j],f[j-a]+1);

                ma=max(ma,f[j]);

            }

        }

    }

    // PIar(f,t+3)

    int ti=t;

    while(f[ti]!=ma) ti--;

    if (ma==0){

        printf("Case %d: %d %d\n",++K,1,678 );

    }

    else {

        printf("Case %d: %d %d\n",++K,ma+1,ti+678 );

    }

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("1.in", "r", stdin);

    freopen("1.out","w",stdout);

#endif

//iostream::sync_with_stdio(false);

//cin.tie(0), cout.tie(0);

    int T;cin>>T;while(T--)

    Solve();

    return 0;

}