Jin Ge Jin Qu hao UVA - 12563 劲歌金曲 0-1背包问题

题目链接 

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

【分析】
虽说t≤109，但由于所有n＋1首曲子的总长度严格大于t，实际上t不会超过180n＋678。这样就可以转化为0-1背包问题了

注意：<=t-1时间内最多可以选择哪些歌曲使得 (数据1,数据2) 最优. 这里的数据1是歌曲数目, 数据2是歌曲总时长, 且数据1优先.

#include  
#include 
using namespace std;
const int T =180*55+678, GE = 678;
int d[T];
int main(int argc, char** argv) {	int T, cnt = 0;cin>> T;while(T--){int n, t, song;cin>> n>> t;memset(d,-1,sizeof(d));d[0] = 0;//标记每次恰好装载的最优更大，便于查找。for(int i = 1; i <= n; i++){cin>> song;for(int j = t-1; j >= song; j--)d[j] = max(d[j], d[j-song]+1);}int id = t-1;for(int i = t-1; i >= 0; i--)if(d[i] > d[id])  id = i;cout<< "Case "<< ++cnt << ": " << d[id]+1 << ' '<< id+GE << '\n';} return 0;
}

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