UVA12563 Jin Ge Jin Qu hao（01背包）

传送门

---

1.一开始以为是01背包的板子，便设计了两个数组一个记录在时间j时最多唱的歌，另一个记录在时间j下最多唱多长时间（有点别扭）。然后wa了，再读题发现题目要求先尽量满足总曲目，再保证时间尽量长，然后这样更新：

if(d[i-x]+1>=d[i]){
	f[i]=max(f[i],f[i-x]+x);
	d[i]=max(d[i],d[i-x]+1);
}

还是WA，无奈之下求助题解，然后发现了这道题和01背包不同的地方

2.回想DAG模型，此题满足DAG。对于曲目来说，这是一个终点不定，起点确定(0)的DAG最长路。参考硬币问题和背包九讲，我们需要将状态d(i)定义为时间i时能唱的最大曲目，而不是时间i内。因此初始化要特别注意，除了d[0]初始化为0,其他均初始化为-inf。不难发现当前唱的最长时间对应最大曲目的最大下标

PS：memset(d,0x8f,sizeof d)即可初始化为-inf，数字大概为-1.8e⁹

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

int d[maxn];

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t,n,m,x,kase=0;
    cin>>t;
    while(t--){
        cin>>n>>m;  //m在下面操作时至少预留1个时间单位
        memset(d,0x8f,sizeof d);
        d[0]=0;
        for(int i=1;i<=n;i++){
            cin>>x;
            for(int j=m-1;j>=x;j--){
                d[j]=max(d[j],d[j-x]+1);
            }
        }
        int ans=0,sum=0;
        for(int i=0;i<=m-1;i++){
            if(sum<=d[i]){
                ans=i;
                sum=d[i];
            }
        }
        cout<<"Case "<<++kase<<": "<<sum+1<<" "<<ans+678<<endl;
    }
    return 0;
}