UVA12563 劲歌金曲 Jin Ge Jin Qu hao（01背包）

整理的算法模板合集： ACM模板

(如果当你看到这个标题的时候笑了，那么这个问题是为你准备的ヽ(￣▽￣)ﾉ)
如果问一个麦霸：“你在KTV里必唱的曲目有哪些？”得到的答案通常都会包含一首“神曲”：古巨基的《劲歌金曲》。为什么呢？一般来说，KTV不会在“时间到”的时候鲁莽地把正在唱的歌切掉，而是会等它放完。例如：在还有15秒时再唱一首2分钟的歌，则实际上多唱了105秒。但是融合了37首歌曲的《劲歌金曲》长达11分18秒，如果唱这首，则相当于多长了663秒！
假设你正在唱KTV，还剩t秒时间。你决定接下来只唱你最爱的n首歌（不含《劲歌金曲》）中的一些，在时间结束之前再唱一个《劲歌金曲》，使得唱的总曲目尽量多（包含《劲歌金曲》），在此前提下尽量晚的离开KTV。
输入n(n<=50)，t(t<=10的9次方)和每首歌的长度(保证不超过3分钟)，输出唱的总曲目以及时间总长度。输入保证所有n+1首曲子的总长度严格大于t。

实际上就是一道01背包模板，根据题意，我们最后一秒要留出来给劲（jing）歌金曲，然后就是正常的01背包。

注意写这类的题目的时候要注意设置边界，因为答案有可能是0，所以我们f数组要初始化为0xcf而不是默认值 0。

#include
#include
#include
#include#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;const int N = 500007, M = 5e3 +7, maxn = 1007;
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f;int n, m;
int f[N];//表示的是到i秒时，最多能唱的曲目数目
int a[N];
int kcase;
int t, ans;int main()
{scanf("%d", &t);while(t -- ){memset(f, 0xcf, sizeof f);//注意初始化为0xcf，因为数据可能为0scanf("%d%d", &n, &m);f[0] = 0;//初始化for(int i = 1; i <= n; ++ i){int tim;scanf("%d", &tim);for(int j = m - 1; j >= tim; -- j){f[j] = max(f[j], f[j - tim] + 1);}}ans = m - 1;for(int i = m - 1; i >= 0; -- i){//因为最后要求总时间尽可能的长if(f[i] > f[ans]){ans = i;}}printf("Case %d: ", ++ kcase);printf("%d %d\n", f[ans] + 1, ans + 678);//输出总曲目以及总时间}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！