首页 > 代码库 > 洛谷P2736 “破锣摇滚”乐队 Raucous Rockers
洛谷P2736 “破锣摇滚”乐队 Raucous Rockers
P2736 “破锣摇滚”乐队 Raucous Rockers
- 21通过
- 52提交
- 题目提供者该用户不存在
- 标签USACO
- 难度普及+/提高
讨论 题解
最新讨论
- 暂时没有讨论
题目描述
你刚刚继承了流行的“破锣摇滚”乐队录制的尚未发表的N(1 <= N <= 20)首歌的版权。你打算从中精选一些歌曲，发行M(1 <= M <= 20)张CD。每一张CD最多可以容纳T(1 <= T <= 20)分钟的音乐，一首歌不能分装在两张CD中。
不巧你是一位古典音乐迷，不懂如何判定这些歌的艺术价值。于是你决定根据以下标准进行选择：
1.歌曲必须按照创作的时间顺序在所有的CD盘上出现。(注：第i张盘的最后一首的创作时间要早于第i+1张盘的第一首)
2.选中的歌曲数目尽可能地多
输入输出格式
输入格式：
第一行： 三个整数：N, T, M.
第二行： N个整数，分别表示每首歌的长度，按创作时间顺序排列。
输出格式：
一个整数，表示可以装进M张CD盘的乐曲的最大数目。
输入输出样例
输入样例#1：
4 5 24 3 4 2
输出样例#1：
3
说明
题目翻译来自NOCOW。
USACO Training Section 3.4
分析：一开始看成模拟了......这是一道比较简单的搜索题，因为要求按顺序放乐曲，所以考虑这个乐曲能不能放和放不放，放是放在这个cd还是下一个cd,判断4种情况即可.
#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>using namespace std;int n, tt, m,a[30],ans = 0;void dfs(int s, int c, int t, int r){ if (s == n + 1 || c == m + 1) { ans = max(ans, r); return; } if (r + n - s + 1<= ans) return; if (t >= a[s]) { dfs(s + 1, c, t - a[s], r + 1); dfs(s + 1, c, t, r); } else { dfs(s + 1, c, t, r); dfs(s, c + 1, tt, r); }}int main(){ scanf("%d%d%d", &n, &tt, &m); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); dfs(1, 1, tt, 0); printf("%d\n", ans); return 0;}
洛谷P2736 “破锣摇滚”乐队 Raucous Rockers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。