题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4008
题目大意：
如果问一个麦霸：“你在KTV里必唱的曲目有哪些？”得到的答案通常都会包含一首“神 曲”：古巨基的《劲歌金曲》。为什么呢？一般来说，KTV不会在“时间到”的时候鲁莽地把 正在唱的歌切掉，而是会等它放完。例如，在还有15秒时再唱一首2分钟的歌，则实际上多 唱了105秒。但是融合了37首歌曲的《劲歌金曲》长达11分18秒(5)，如果唱这首，相当于多 唱了663秒！
假定你正在唱KTV，还剩t秒时间。你决定接下来只唱你最爱的n首歌（不含《劲歌金 曲》）中的一些，在时间结束之前再唱一个《劲歌金曲》，使得唱的总曲目尽量多（包含 《劲歌金曲》），在此前提下尽量晚的离开KTV。
输入n（n≤50），t（t≤109）和每首歌的长度（保证不超过3分钟(6)），输出唱的总曲目 以及时间总长度。输入保证所有n＋1首曲子的总长度严格大于t。

大概意思是：有n首歌曲，和一首《劲歌金曲》,有时间t，问你最多能唱多少首歌，如果有几个方案，选择总时间最长的方案。（虽说t≤10^9，但由于所有n＋1首曲子的总长度严格大于t，实际上t不会超过180n＋678。 这样就可以转化为0-1背包问题了。）

思路：刚开始想到了用dp[i][j]表示前i首歌中唱j首的最短时间。然后找到第一个dp[n][j]输出，回来发现不对，dp[i][j]表示最短时间和最长时间都有问题，选择最大，可能让有解变无解，选择最小，可能导致无法取得最优解。

题解有两种思路：
思路一：
用即f[j]表示的是在j的时间恰好用完的情况下最多能唱多少首歌。那么再记录一个最多的歌曲数。再遍历一次就可以找到最长的时间了。
(为什么要刚好用完呢？：https://www.cnblogs.com/shi2015/p/4661971.html)
ps：气死我了，01背包写错了 dp[i][j]=max(dp[i-1][j-a[i]]+1, dp[i-1][j])写成 dp[i][j]=max(dp[i-1][j-a[i]]+1, dp[i][j]);debug一下午。还可以用滚动数组优化。

思路二：
跟普通的01背包有区别的是：要保证两个条件取得最优。那么我们可以把状态用结构体来描述。

我们令dp[i][j]==x 表示当决策完全前i个物品后(选或不选), 所选的总歌曲时长<=j时, 所得到的最优状态为x. (这里的x就不是平时我们所说的最长时间或最多歌曲数目了)

怎么理解最优状态为x这个事实呢? 假设有两种选择前i个歌曲的方法能使得决策完前i个物品且总时长<=j时的状态分别为x1 和x2.

1.那么如果x1状态的歌曲数目> x2状态的歌曲数目, 那么明显x1状态更优. 
所以dp[i][j]应==x1.

2.如果x1状态的歌曲数目与x2的相等, 但是x2状态的时长 > x1状态时长, 
那么此时x2状态更优. 所以dp[i][j]应==x2.

重载运算符就ok了。

经过上面的分析,我们可以用一个(具有歌曲数和总时长双属性的)结构体来表示一个状态. 且可以得到下面状态转移公式:

dp[i][j] = 最优( dp[i-1][j] , 在dp[i-1][j-t[i]]的基础上选择第i首歌后得到的新状态tmp )

所有dp初始化为0即可. 最终我们所求为dp[n][max_time]

//方法一
#include <bits/stdc++.h>
#define LL long long
using namespace std;
int dp[55][10000];
int a[55];
int main()
{
    int t, CUT=1;
    scanf("%d",&t);
    while(t--)
    {
        int n, T, Max=0;
        scanf("%d%d",&n,&T);
        T--;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        memset(dp, 0, sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=T;j++)
            {
                if(j>=a[i]&&dp[i-1][j-a[i]]>=1||j-a[i]==0)
                {
                    dp[i][j]=max(dp[i-1][j-a[i]]+1, dp[i-1][j]);
                }
                else
                {
                    dp[i][j]=dp[i-1][j];
                }
                Max=max(dp[i][j], Max);
            }
        }
        //滚动数组
        //for(int i = 1; i <= n; i++)
		//{
		// for(int j = T; j >= a[i]; j--)
		// {
		// if(dp[j - a[i]] >= 1|| j == a[i]) //在j时间内可以唱完第i首歌。
		// {
		// dp[j] = max(dp[j], dp[j - a[i]] + 1);
		// Max = max(Max, dp[j]);
		// }
		// }
		//}

        if(Max==0)
        {
            printf("Case %d: %d %d\n",CUT++, 1, (11)*60+18);
            continue;
        }

        for(int i=T;i>=1;i--)
        {
            if(dp[n][i]==Max)
            {
                printf("Case %d: %d %d\n",CUT++, Max+1, i+(11)*60+18);
                break;
            }
        }
    }

    return 0;
}


//方法二：
#include <bits/stdc++.h>
#define LL long long
using namespace std;

struct node
{
    int n;//歌曲数
    int t;//时间数
    bool operator <(node &a)
    {
        if(n!=a.n)
        {
            return n<a.n;
        }
        else
        {
            return t<a.t;
        }
    }
};

node dp[10000];
int a[55];
int main()
{
    int t, CUT=1;
    scanf("%d",&t);
    while(t--)
    {
        int n, T, Max=0;
        scanf("%d%d",&n,&T);
        T--;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        memset(dp, 0, sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            for(int j=T;j>=a[i];j--)
            {
                node x=node{dp[j-a[i]].n+1, dp[j-a[i]].t+a[i]};
                if(dp[j]<x)
                {
                    dp[j]=x;
                }
            }
        }
        printf("Case %d: %d %d\n",CUT++, dp[T].n+1,dp[T].t+678);
    }

    return 0;
}