UVa 12563 - Jin Ge Jin Qu hao（01背包）

发表于 分类于 ， Disqus：

给出剩余时间和想唱的歌，求最多能唱几首和最长时间。

较为简单的01背包问题，在算数目的时候顺便计算时间就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=180*55+678;
int song[55],f[maxn],k[maxn];
int main(){
    int t,tt=0;
    cin>>t;
    while(t--){
        memset(f,0,sizeof(f));
        memset(k,0,sizeof(k));
        memset(song,0,sizeof(song));
        int n,t,cnt=1,len=678;
        cin>>n>>t;
        --t;
        for(int i=0;i<n;++i)
            cin>>song[i];
        for(int i=0;i<n;++i)
            for(int j=t;j>=song[i];--j){
                if(f[j-song[i]]+1>f[j]||(f[j-song[i]]+1==f[j]&&k[j-song[i]]+song[i]>k[j])){
                    f[j]=f[j-song[i]]+1;
                    k[j]=k[j-song[i]]+song[i];
                }
            }
        cnt+=f[t],len+=k[t];
        cout<<"Case "<<++tt<<": "<<cnt<<" "<<len<<endl;
    }
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

相关文章