P2736 “破锣摇滚”乐队 Raucous Rockers

admin

https://www.luogu.org/problemnew/show/P2736

题目描述
你刚刚继承了流行的“破锣摇滚”乐队录制的尚未发表的N(1 <= N <= 20)首歌的版权。你打算从中精选一些歌曲，发行M(1 <= M <= 20)张CD。每一张CD最多可以容纳T(1 <= T <= 20)分钟的音乐，一首歌不能分装在两张CD中。CD数量可以用完，也可以不用完

不巧你是一位古典音乐迷，不懂如何判定这些歌的艺术价值。于是你决定根据以下标准进行选择：

1.歌曲必须按照创作的时间顺序在所有的CD盘上出现。(注：第i张盘的最后一首的创作时间要早于第i+1张盘的第一首)

2.选中的歌曲数目尽可能地多

输入输出格式
输入格式：
第一行： 三个整数：N, T, M.

第二行： N个整数，分别表示每首歌的长度，按创作时间顺序排列。

输出格式：
一个整数，表示可以装进M张CD盘的乐曲的最大数目。

输入输出样例
输入样例#1：
4 5 2
4 3 4 2
输出样例#1：
3
说明
题目翻译来自NOCOW。

USACO Training Section 3.4

张笑宇

1. #include<iostream>
   
2. using namespace std;
   
3. int n,m,t,ans=-1,s=1;
   
4. int cd[25],tim[25];
   
5. void dfs(int x,int sum)
   
6. {
   
7.     if(sum+n+1-x<=ans) return;
   
8.     if(x==n+1)
   
9.     {
   
10.         ans=max(ans,sum);
    
11.         return;
    
12.     }
    
13.     if(cd[s]>=tim[x])
    
14.     {
    
15.         cd[s]-=tim[x];
    
16.         dfs(x+1,sum+1);
    
17.         cd[s]+=tim[x];
    
18.     }
    
19.     if(s<m&&t>=tim[x])
    
20.     {
    
21.         s++;
    
22.         cd[s]-=tim[x];
    
23.         dfs(x+1,sum+1);
    
24.         cd[s]+=tim[x];
    
25.         s--;
    
26.     }
    
27.     dfs(x+1,sum);
    
28. }
    
29. int main()
    
30. {
    
31.     cin>>n>>t>>m;
    
32.     for(int i=1;i<=n;i++) cin>>tim[i];
    
33.     for(int i=1;i<=m;i++) cd[i]=t;
    
34.     dfs(1,0);
    
35.     cout<<ans;
    
36.     return 0;
    
37. }
    

复制代码

黄煦喆

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. int n,m,t;
   
4. int a[21],f[21][21];
   
5. int main()
   
6. {
   
7.     cin>>n>>t>>m;
   
8.     for(int i=1;i<=n;i++)cin>>a[i];
   
9.     for(int i=1;i<=n;i++)
   
10.         for(int j=m;j>=1;j--)
    
11.             for(int k=t;k>=a[i];k--)
    
12.                 f[j][k]=max(f[j][k],max(f[j-1][t]+1,f[j][k-a[i]]+1));
    
13.     cout<<f[m][t];
    
14.     return 0;
    
15. }
    

复制代码

walk_alone

1. #include <cstdio>
   
2. int max(int a,int b,int c)
   
3. {
   
4.         int t=-999;
   
5.         if(t<a)
   
6.                 t=a;
   
7.         if(t<b)
   
8.                 t=b;
   
9.         if(t<c)
   
10.                 t=c;
    
11.         return t;
    
12. }
    
13. int time[21],f[21][21];
    
14. int main()
    
15. {
    
16.         int n,m,t;
    
17.         scanf("%d%d%d",&n,&t,&m);
    
18.         for(int i=1;i<=n;i++)
    
19.                 scanf("%d",&time[i]);
    
20.         for(int i=1;i<=n;i++)
    
21.                 for(int j=m;j>=1;j--)
    
22.                         for(int k=t;k>=time[i];k--)
    
23.                     f[j][k]=max(f[j][k],f[j-1][t]+1,f[j][k-time[i]]+1);
    
24.         printf("%d",f[m][t]);
    
25.         return 0;
    
26. }

复制代码