用一个vector保存所有歌曲时间，先对歌曲时间排序，前n-1首歌曲均为选放，而最后一首也就是最长一首为必放，也就是用t-1大小的背包存n-1首歌，转化为简单的01背包问题就可以写代码了 
#include<bits/stdc++.h>
using namespace std;
int main(){
    int T,n,t,k;
    vector<int> singtime;
    cin>>T;
    while(T--){
        singtime.clear();
        cin>>n>>t;
        for(int i=0;i<n;i++){
            cin>> k;
            singtime.push_back(k);
        }
        sort(singtime.begin(),singtime.end());
        int dp[n][t];
        fill_n(&dp[0][0],n*t,0);
        for(int i=1;i<n;i++){
            for(int j=0;j<t;j++){if(j<singtime[i-1]) dp[i][j]=dp[i-1][j];
                                 else 
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-singtime[i-1]]+singtime[i-1]);
            }
        }
        cout<<dp[n-1][t-1]+*(singtime.end()-1)<<endl;
        
    }
}