整数 font 标准 出现 can lib ini auc strong
你刚刚继承了流行的“破锣摇滚”乐队录制的尚未发表的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盘的乐曲的最大数目。
- 4 5 2
- 4 3 4 2
- 3
题目翻译来自NOCOW。
USACO Training Section 3.4
题目大意:m首歌,n个cd,每首歌有时间,然后每个cd最多放的时间是t,必须按顺序放入cd,最多能放几首歌。
题解1:
dfs 每一首歌的状态是放入当前cd,放入下一个cd,不放入cd。
- #include < iostream > #include < cstdio > #include < cstring > using namespace std;
- int n,
- t,
- m,
- ans,
- tot = 1,
- tim[22],
- cd[22];
- void dfs(int now, int sum) {
- if (n - now + 1 + sum <= ans) return;
- if (now == n + 1) {
- ans = max(ans, sum);
- return;
- }
- if (tim[now] <= cd[tot]) {
- cd[tot] -= tim[now];
- dfs(now + 1, sum + 1);
- cd[tot] += tim[now];
- }
- if (tot < m && t >= tim[now]) {
- tot++;
- cd[tot] -= tim[now];
- dfs(now + 1, sum + 1);
- cd[tot] += tim[now];
- tot--;
- }
- dfs(now + 1, sum);
- }
- int main() {
- scanf("%d%d%d", &n, &t, &m);
- for (int i = 1; i <= n; i++) scanf("%d", &tim[i]);
- for (int i = 1; i <= m; i++) cd[i] = t;
- dfs(1, 0);
- printf("%d\n", ans);
- return 0;
- }
题解2:
参考洛谷物是人非...
f[i]表示时间i能装的最多的唱片的数量,答案为f[t*m],为了避免唱片被分割的情况,
如果tim[k]<=i%t,如果第k个唱片时间小于残缺的长篇的时间则加入,否则加入完整的唱片。
- #include < iostream > #include < cstdio > using namespace std;
- int t,
- m,
- n,
- a[22],
- f[500];
- int main() {
- scanf("%d%d%d", &n, &t, &m);
- for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
- for (int i = 1; i <= n; i++) {
- for (int j = t * m; j >= 1; j--) {
- if (a[i] <= j % t) f[j] = max(f[j], f[j - a[i]] + 1);
- else if (a[i] <= j / t * t) f[j] = max(f[j], f[j / t * t - a[i]] + 1);
- }
- }
- cout << f[t * m];
- return 0;
- }
题解3:f[i][j]表示前i张唱片,第i张唱片的时间为j的最大值。
by shenben
- #include < cstdio > #include < cstdlib > #include < iostream > using namespace std;#define N 22 int n,
- m,
- t,
- v[N],
- f[N][N]; //f[k][j] k张CD,第k张CD的容量为j的最大数量
- int main() {
- scanf("%d%d%d", &n, &t, &m);
- for (int i = 1; i <= n; i++) scanf("%d", &v[i]);
- for (int i = 1; i <= n; i++) {
- for (int k = m; k; k--) {
- for (int j = t; j >= v[i]; j--) {
- f[k][j] = max(f[k][j], max(f[k - 1][t], f[k][j - v[i]]) + 1);
- }
- }
- }
- printf("%d", f[m][t]);
- return 0;
- }
洛谷P2736 “破锣摇滚”乐队 Raucous Rockers
来源: http://www.bubuko.com/infodetail-2319305.html