链接：https://ac.nowcoder.com/acm/problem/25184
来源：牛客网
题目描述
网易云音乐推出了定时关闭播放的功能，假设到了定时关闭播放的时间，当前这首歌还没有播放完，那就把它播放完关闭；如果到了定时关闭的时间，当前歌恰好播放完，那就立即关闭。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单位时间的歌。
思路：不管前面怎么听歌，只要能在最后时间听到最长的歌即可。换言之，在t-1时间听歌时长最大的同时，在t时间开始听最长的歌，两者时间之和，就是我们要求的最长听歌时间ans。
具体解决：按照思路，代码中，我们要找出max（a[i]），并求t-1时间最大听歌时长。找出最大的a[i]排序即可解决，求t-1时间最大听歌时长，就是求一个01背包问题：在n-1首歌中，装满一个容量为t-1的背包的最大价值，每首歌的价值为a[i]。（这道题很巧的是容量单位是时间，价值单位也是时间，按理说应该有简便算法，但是这样的01背包已经算简单的了!）
转移方程: dp[i] ：i时间内的最大听歌时长
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int T, n, t, ans;
int a[201], dp[800010];
void solve() {
cin >> T;
while (T -- ) {
// 输入
cin >> n >> t;
for (int i = 0; i < n; i ++) {
cin >> a[i];
}
// 排序确定最长的歌
sort(a, a + n);
memset(dp, 0, sizeof(dp));
for (int i = 0; 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]);
}
}
// 更新ans
ans = dp[t - 1] + a[n - 1]; // 容量为t-1的背包的最大值 + 最后（最长）一首歌时长
cout << ans << endl;
}
return;
}
int main() {
solve();
return 0;
}
标签：int,听歌,首歌,---,牛客,时间,播放,CSP,dp From： https://www.cnblogs.com/yumomo/p/16983572.html