NC25184. 简单的烦恼
描述
网易云音乐推出了定时关闭播放的功能，假设到了定时关闭播放的时间，当前这首歌还没有播放完，那就把它播放完关闭；如果到了定时关闭的时间，当前歌恰好播放完，那就立即关闭。xrc 在知道网易云这个算法后，想知道如果自己定时 t 时间后关闭播放，那最多能听多长时间的歌，已知 xrc 歌单中一共有 n 首歌，并且知道每首歌的播放时间分别是 a[i]。
输入描述
第一行一个整数T(T <=
23)，表示数据组数。
在每组输入数据中，第一行有两个正整数，n(n
<= 200), t(t <= 80000)，分别表示歌单中歌曲的数目，和题目描述中的t。
第二行中有n个正整数a[i](a[i] <= 400),表示每首歌曲的时间长度。
输出描述
对于每组数据，输出一个ans，表示最多能听多长时间的歌曲。
示例1
输入:
1 3 7 4 3 2
输出:
9
说明:
先听第2首歌和第3首歌，最后播放第1首歌，在7单位时间后，第3首歌还没有播放完，所以要等第1首歌播放完，共能听9单位时间的歌。C++(g++ 7.5.0) 解法, 执行用时: 146ms, 内存消耗: 16068K, 提交时间: 2023-07-25 15:31:31
#include<bits/stdc++.h>
using namespace std;
const int N=2000001;
long long a[N],b[N];
int main()
{
int T;
cin>>T;
while(T--)
{
memset(b,0,sizeof(b));
int n,t;
cin>>n>>t;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n);
for(int j=1;j<=n-1;j++)
{
for(int k=t-1;k>=a[j];k--)
b[k]=max(b[k],b[k-a[j]]+a[j]);
}
cout<<b[t-1]+a[n]<<endl;
}
}
C++(clang++11) 解法, 执行用时: 259ms, 内存消耗: 736K, 提交时间: 2021-05-12 21:19:31
#include<bits/stdc++.h>
using namespace std;
int t,n,a[210],l,f[80005];
int main(){
cin>>t;
while(t--){
cin>>n>>l;
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
memset(f,0,sizeof(f));
for(int v=0;v<n-1;v++)
for(int i=l-1;i>=a[v];i--){
f[i]=max(f[i],f[i-a[v]]+a[v]);
}
cout<<f[l-1]+a[n-1]<<endl;
}
}