UVA 12563 劲歌金曲(01背包)

劲歌金曲

【题目类型】01背包

&题解：

题意：求在给定时间内，最多能唱多少歌曲，在最多歌曲的情况下，使唱的时间最长。
该题类似于01背包问题，可用01背包问题的解题思路来求，每个歌曲相当于物品，歌曲的长度相等于物品重量，每个歌曲的“价值”为1。由于金歌劲曲时间最长，所以最后要留至少1秒时间开始唱金歌劲曲，所以计算t-1时间内最多唱的歌曲和时间，最终答案为歌曲数加1，时间加上金歌劲曲的时间。这里我使用滚动数组计算这个值，用len记录t-1。
需要注意的是，由于要求是连续唱歌，且要求在最多歌曲数的情况下时间最长，如果按普通的背包存储，很难得到最长时间，因为f[len] 只存储了最多的歌曲数，但并不知道这些歌曲到底唱了多少时间。假设最多歌曲数为num, 唱num首歌曲最少时间为tmin, 那么数组中从f[tmin]到f[len]都等于num,我们无法得知唱num首歌的最大时间。比如说len = 10, t[1] = 5, t[2] = 8, 那么f[5] 到 f[10] 都等于1，无法知道唱从5到10哪个是唱1首歌的最长时间。如何处理呢？
这里需要用到一个技巧：对决策进行一定的限定！ 在计算某个时间最多唱的歌曲时，必须是该时间内恰好唱完这些歌，时间多了不行。即f[j]表示的是在j 的时间恰好用完的情况下最多能唱多少首歌。比如上面的例子只有f[5] 和f[8]等于1，其他的都等于0。这样的话处理时先算出最多唱的歌曲数 num，然后从j = len开始遍历数组f, 第一个等于num的就是在最多歌曲情况下的最长时间。
参考于：http://blog.csdn.net/yanzheshi/article/details/47086461

这是01背包的变形，但上面的想法确实很巧妙，也就是巧妙在定义f数组所表示的状态的时候，真的应该学习下这种分析问题的过程。
【时间复杂度】O(n*10000)

&代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf("%d",&(N))
#define SII(N,M) scanf("%d %d",&(N),&(M))
#define SIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i--)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<"="<<(x)<<endl;
#define DGG(x,y) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<" "<<#z<<"="<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<" ";cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<" ";cout<<endl;}
const double EPS = 1e-9 ;
/*  ////////////////////////   C o d i n g  S p a c e   ////////////////////////  */
const int MAXN = 10000 + 9 ;
int K,n,t,a,f[MAXN];
void Solve()
{
    cle(f,0);
    int ma=0;
    SII(n,t); t--;
    rep(i,n){
        SI(a);
        red(j,t,a){
            if (f[j-a]||j==a){
                f[j]=max(f[j],f[j-a]+1);
                ma=max(ma,f[j]);
            }
        }
    }
    // PIar(f,t+3)
    int ti=t;
    while(f[ti]!=ma) ti--;
    if (ma==0){
        printf("Case %d: %d %d
",++K,1,678 );
    }
    else {
        printf("Case %d: %d %d
",++K,ma+1,ti+678 );        
    }
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("1.out","w",stdout);
#endif
//iostream::sync_with_stdio(false);
//cin.tie(0), cout.tie(0);
    int T;cin>>T;while(T--)
    Solve();
    return 0;
}