UVa 12563 - Jin Ge Jin Qu Hao(01背包)

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

较为简单的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博客 ,格式可能有所偏差。