题解 | #简单的烦恼#
简单的烦恼
https://ac.nowcoder.com/acm/problem/25184
用一个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;
}
}
睿联技术公司福利 32人发布
投递数字马力等公司6个岗位 >
查看14道真题和解析