背包问题（思路+分析）

这题思路就是：讲最场的歌曲在最后一分钟播放，剩下n-1首歌曲在t-1时间内求最大值
以例子演示一下：
注意这里最大时长已经被预订最后一分钟播放

1   2   3   4   5   6
0   0   0   0   0   0
先加入时长为2的歌曲变为
0   2   2   2   2   2
加入时长为3的歌曲
0   2   3   3   5   5
最后返回的结果为dp[6]+a[n]即9
#include<bits/stdc++.h>
using namespace std;
int a[205],n,t;
int dp[80005];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(dp,0,sizeof(dp));
        scanf("%d%d",&n,&t);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        sort(a+1,a+n+1);//从小到大排序
        for(int i=1;i<=n-1;i++)//范围是n-1,最大的已经被预订为放在最后一分钟播放
        {
            for(int j=t-1;j>=a[i];j--)//这里是从后往前推，保证每首歌只能听一遍
            {
                dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
            }
        }
        printf("%d\n",dp[t-1]+a[n]);


    }


}