例题9-5 劲歌金曲（Jin Ge Jin Qu [h]ao, Rujia Liu's Present 6, UVa 12563）

欢迎访问我的Uva题解目录 https://blog.csdn.net/ri*qi/article/details/81149109

题目描述

题意解析

如果问一个麦霸：“你在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&lt;=10^9$t<=109，但是由于n+1首曲子总长度大于t，可以得出$t&lt;180×n+678$t<180×n+678。所以完全可以直接用t作为数组的维度而不至于爆内存。
这是一道典型的0-1背包问题。涉及到两种评价标准：曲子数和曲子总长度。注意先要保证曲子数尽可能多，在曲子数同样多的情况下取曲子总长度更长的。可以定义一个pair<int,int>类型的二维数组dp，用first成员存储曲子数，用second成员存储曲子总长度，而pair类型已经内置了小于运算符，即先比较first成员，再比较second成员，正好与本题要求相符。那么dp[i][j]可以表示在剩余时间为$j$j的情况下，把$i,i+1,i+2,...,n$i,i+1,i+2,...,n首曲子都播放的曲子数和曲子总长度。可以得到状态转移方程为$dp(i,j)=max\{dp(i+1,j),\{dp(i+1,j-length[i]).first+1,dp(i+1,j-length[i]).second+length[i]\}\}$dp(i,j)=max{dp(i+1,j),{dp(i+1,j−length[i]).first+1,dp(i+1,j−length[i]).second+length[i]}}
当然，本题也可以用滚动数组来求解。以下给出记忆化搜索、递推和滚动数组三种形式的代码。

记忆化搜索的C++代码

#include<bits/stdc++.h>
using namespace std;
int T,n,t,length[55];
pair<int,int>dp[55][180*55+678];
pair<int,int> DP(int i,int j){
    if(dp[i][j].first!=-1)//该dp数组已经访问过，直接返回值
        return dp[i][j];
    if(i==n-1)//边界情况
        return dp[i][j]=(j>length[i])?make_pair(2,length[i]+678):make_pair(1,678);
    dp[i][j]=DP(i+1,j);
    if(j>length[i])
        dp[i][j]=max(DP(i+1,j),{DP(i+1,j-length[i]).first+1,DP(i+1,j-length[i]).second+length[i]});
    return dp[i][j];
}
int main(){
    scanf("%d",&T);
    for(int ii=1;ii<=T;++ii){
        scanf("%d%d",&n,&t);
        for(int i=0;i<n;++i)
            scanf("%d",&length[i]);
        for(int i=0;i<n;++i)//对dp数组初始化
            for(int j=0;j<=t;++j)
                dp[i][j]={-1,-1};
        printf("Case %d: %d %d\n",ii,DP(0,t).first,DP(0,t).second);
    }
    return 0;
}

递推的C++代码

#include<bits/stdc++.h>
using namespace std;
int T,n,t,length[55];
pair<int,int>dp[55][180*55+678];
int main(){
    scanf("%d",&T);
    for(int ii=1;ii<=T;++ii){
        scanf("%d%d",&n,&t);
        for(int i=0;i<n;++i)
            scanf("%d",&length[i]);
        for(int i=0;i<=t;++i)//边界
            dp[n-1][i]=(i>length[n-1])?make_pair(2,length[n-1]+678):make_pair(1,678);
        for(int i=n-2;i>=0;--i)
            for(int j=0;j<=t;++j){
                dp[i][j]=dp[i+1][j];
                if(j>length[i])
                    dp[i][j]=max(dp[i][j],{dp[i+1][j-length[i]].first+1,dp[i+1][j-length[i]].second+length[i]});
            }
        printf("Case %d: %d %d\n",ii,dp[0][t].first,dp[0][t].second);
    }
    return 0;
}

滚动数组

#include<bits/stdc++.h>
using namespace std;
int T,n,t,a;
pair<int,int>dp[180*55+678];
int main(){
    scanf("%d",&T);
    for(int ii=1;ii<=T;++ii){
        scanf("%d%d",&n,&t);
        for(int i=0;i<=t;++i)//初始化dp数组
            dp[i]={1,678};
        for(int i=0;i<n;++i){
            scanf("%d",&a);
            for(int j=t;j>=0;--j)
                if(j>a)
                    dp[j]=max(dp[j],{dp[j-a].first+1,dp[j-a].second+a});
        }
        printf("Case %d: %d %d\n",ii,dp[t].first,dp[t].second);
    }
    return 0;
}