Jin Ge Jin Qu hao

  一道01背包，虽然t<=1e9，但实际上t不会超过180 * n + 678。

代码如下:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define INF 0x3fffffff
#define JIN 678
#define mst(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e5+5;
int time_[1000];
int dp[maxn];
void init()
{    
    memset(dp,0x8f,sizeof(dp));
    dp[0]=0;
}
int main()
{
    int T;
    int kase=0;
    cin>>T;
    while(T--)
    {    
        mst(time_,0);init();
        int n,t_lef;
        cin>>n>>t_lef;
        int cnt=0;
        for(int i=1;i<=n;i++)        cin>>time_[i];
        int vtot=t_lef-1;
        for(int i=1;i<=n;i++){
            for(int j=vtot;j>=time_[i];j--){
                dp[j]=max(dp[j],dp[j-time_[i]]+1);
            }
        }
        int len=t_lef-1;        //留一秒来唱劲歌金曲
        for(int i=vtot;i>=0;i--){
            int tmp=cnt;
            cnt=max(cnt,dp[i]);
            if(cnt!=tmp)
                len=i;
        }
        printf("Case %d: %d %d\n",++kase,cnt+1,len+JIN);        
        //加上劲歌金曲         
    }
    return 0;
}