首页 > 代码库 > UVA - 12563 Jin Ge Jin Qu hao （01背包变形）
UVA - 12563 Jin Ge Jin Qu hao （01背包变形）
此题应该注意两个点，首先背包容量应该缩减为t-1，因为最长的歌不超过三分钟，而劲歌金曲有678s，所以肯定要留出这个时间来。其次注意优先级，保证唱的歌曲数目最多，在此前提下尽可能的延长时间。
处理方法：开创结构体，在歌曲数目相等的时候，选取最长时间。
注意：注意t的大小，t完全没有必要计算那么大的数据。 代码如下：
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define N 10010int w[55];struct DP{ int song,tim;}dp[N];int main(){// freopen("1.in.cpp","r",stdin); int T,n,t,ca=0,sum; cin>>T; while(T--) { cin>>n>>t; sum = 0; for(int i = 1; i <= n; i++) { cin>>w[i]; sum += w[i]; } if(t > sum){ if(t < sum + 678) t = sum + 678; printf("Case %d: %d %d\n",++ca,n+1,t); continue; } t--; for(int i = 0;i < N;i++) dp[i].song = dp[i].tim = 0; for(int i = 1; i <= n; i++) { for(int j = t; j >= w[i]; j--) { if(dp[j-w[i]].song+1 > dp[j].song) { dp[j].song = dp[j-w[i]].song + 1; dp[j].tim = dp[j-w[i]].tim + w[i]; } if(dp[j-w[i]].song+1 == dp[j].song) { dp[j].tim = max(dp[j].tim,dp[j-w[i]].tim + w[i]); } } } printf("Case %d: %d %d\n",++ca,dp[t].song+1,dp[t].tim+678); } return 0;}
UVA - 12563 Jin Ge Jin Qu hao （01背包变形）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。