题解 | #简单的烦恼#

原题传送门

题目理解

这道题说是简单的烦恼，其实也十分简单。
将题目简单整理一下：

1. 你的歌单里有 首歌。
2. 歌单里的每一首歌的时长为 ，其中 为一个长度为 的序列。
3. 你设置了一个 个单位时间的定时关闭。
4. 定时关闭时间到达之后，将正在播放的最后一首歌放完后关机。
5. 你想使得你听歌曲的时间最长，问最多是多少时间。
6. 这题有 组 测试数据。

解法思路

之后，我们来想一想解法：
换作我，如果我想让我所听时间最长，我一定会把那首最长的歌在第 个单位时间（结束前的一刻）让它播放。
这样就可以使得听到时间最长。

所以这个问题被转化为了 “在 个单位时间内，听 首（除去最长的那首）曲子”。
也就是说， 再仔细一想，这不就是一个01背包问题吗？其中背包总容量为 ，共有 件物品，每一件物品的体积和价值都是 。

接着，我们考虑一些细节：

1. 这题的每一个测试点都有 组 测试数据，所以如果我们要用动态规划，这个 f[] 数组要用 memset() 清理，同时每一次输出之后要换行，防止出错。
2. 我们如何把 首曲子中最长的那一首从数组中除去呢？这里有两种方法：
   1. 在输入的时候使用两个变量来分别存储最长的歌的长度，和这首歌的下标。然后在循环递推时判断，如果遍历到了那首歌，就直接 continue 。
      2.将数组 a[] 直接升序排个序。循环的时候只循环 a[1]~a[n-1] 最大的那首歌自然就被除去了。

AC 代码

#include<bits/stdc++.h>
using namespace std;
const int N=80005;
int T;
int n,t;
int a[210];
int f[210][N];
int main(){
	cin>>T;
	while(T--){
		memset(f,0,sizeof(f)); // 多测不清空，爆0两行泪
		cin>>n>>t;
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		sort(a+1,a+1+n); // 排序
      	// 二维的01背包
		for(int i=1;i<=n-1;i++){
			for(int j=0;j<=t-1;j++){
				f[i][j]=f[i-1][j];
				if(j>=a[i]){
					f[i][j]=max(f[i][j],f[i-1][j-a[i]]+a[i]);
				}
			}
		}
		cout<<f[n-1][t-1]+a[n]<<endl; // f[n-1][t-1] （t-1个单位时间内的最大值）+ a[n] （最后也是最长的的一首曲子）
	}
	return 0;
}