华师一附中OI组

标题: P2736 “破锣摇滚”乐队 Raucous Rockers [打印本页]
作者: admin    时间: 2018-6-29 18:30
标题: P2736 “破锣摇滚”乐队 Raucous Rockers
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
作者: walk_alone    时间: 2018-7-29 09:16
  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. }
复制代码
作者: 黄煦喆    时间: 2018-7-29 10:35
  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. }
复制代码
作者: 张笑宇    时间: 2018-7-29 11:40
  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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2