[动态规划] UVa12563 劲歌金曲 （01背包问题）

题目

思路

01背包问题
1.状态定义：(i,j), 遍历到i时，剩余时间为T
2.指标函数：d(i,j), 唱了歌数
3.答案：d(n,1~TT), 边界：d[1][TT] = 0, d[1][TT-time[1]] = 1;
4.状态转移方程：

d(i,j)={d(i−1,j),d(i−1,j+time[i]+1)}$$d(i,j)=\left\{d(i-1,j),d(i-1,j+time[i]+1)\right\}$$

5.本题折腾了很久，一个难点在于必须不停唱歌，不能停。也就是将d(1,0~TT-1)先赋值为-INF（除了TT-time[1]），意思是不能达到，就是不存在此种状态。（也就是刚开始要么唱，要么不唱，没有等一会再唱的情况）。这种情况下，再递推i=1的情况有点麻烦，所以我就手推了，递推时从i=2开始。
6.输出时，找到最大ans，再找最大ans里的最小剩余时间即可。

代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define _for(i,a,b) for(int i = (a); i<(b); i++)
#define _rep(i,a,b) for(int i = (a); i<=(b); i++)
using namespace std;

const int INF = 1<<30;
const int maxn = 50+5;
const int maxx = 10000; // 180n + 678
int n, TT, d[maxn][maxx], time[maxn]; 

int main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int T,kase = 0;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&TT);
        _rep(i,1,n) scanf("%d",&time[i]);

        _rep(i,0,TT) d[1][i] = -INF;
        d[1][TT] = 0;
        if (TT >= time[1]) d[1][TT-time[1]] = 1;
        _rep(i,2,n)
            _rep(T,0,TT){
                int d1 = d[i-1][T];
                int d2 = -INF;
                if (T+time[i] <= TT) d2 = d[i-1][T+time[i]] + 1;
                d[i][T] = max(d1,d2);
            }

        int ans = 0, anst = 0;
        _rep(i,1,TT) ans=max(ans,d[n][i]);
        _rep(i,1,TT)
            if(d[n][i] == ans){
                anst = TT-i+678;
                break;
            }
        printf("Case %d: %d %d\n",++kase,ans+1,anst);
    }
    return 0;
}