本文共 851 字，大约阅读时间需要 2 分钟。
这道题可以用DP来做，实质上是个背包模型，因为它有一个费用t。
状态：dp[i,j]表示前i首歌，在j分钟内可以听的歌曲的总时长。 状态转移方程： dp[i,j]= if(j<song[i]) dp[i-1,j]; else max(dp[i-1,j],dp[i-1,j-song[i]]+song[i])； 在这里要注意一下：因为我们要选出最接近时间t的歌曲的时间总和sum（不能>=t），然后sum+max(song[i])，这样才可以使时间最长。因此j的范围是[song[i],t-1]。 这里的j和dp[i,j]所表示的意义都是时间，说明背包中DP对象以及DP意义的物理意义是可以一样——其实只要有费用，就可以想到用背包模型来做。代码如下：
#include#include #include #include #include typedef long long ll;using namespace std;const int inf=0x3f3f3f3f;const int maxn=8e4+5;int dp[maxn],s[205]; //用了滚动数组int main(){ int T,n,t,i,j; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&t); memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) scanf("%d",&s[i]); sort(s+1,s+1+n); dp[0]=0; for(i=1;i<=n-1;i++) //i止于n-1 for(j=t-1;j>=s[i];j--) dp[j]=max(dp[j],dp[j-s[i]]+s[i]); printf("%d\n",dp[t-1]+s[n]); } return 0;}
转载地址：http://jddci.baihongyu.com/