USACO3.4 “破锣摇滚”乐队 Raucous Rockers - DP

https://www.luogu.com.cn/problem/P2736
题意
给定 $N（1\le N\le 20）$ 首歌，从中选出若干首歌曲，发行 $M（1\le M\le 20）$ 张 CD。
每张 CD 最多容纳 $T（1\le T\le 20）$ 分钟的音乐，一首歌不能分装在两张 CD 中。CD 数量可以用完，也可以不用完。

根据以下标准进行选择：

1. 歌曲必须按照创作的时间顺序在所有的 CD 盘上出现。(注：第 $i$ 张盘的最后一首的创作时间要早于第 $i+1$ 张盘的第一首)
2. 选中的歌曲数目尽可能地多。

问，能够装进 $M$ 张 CD 的最多歌曲数量？

思路
“歌曲必须按照创作的时间顺序在所有的 CD 盘上出现” 这个条件说明不能直接贪心。
考虑用dp，当前容量中最多能够存储的歌曲数量从减掉当前歌曲大小的容量来转移。
而 “一首歌不能分装在两张 CD 中” 这个条件就说明不能简单的从上一个容量来转移，还需要考虑是否分装在两张中。

所以，定义状态 f[i, j, k] 表示，对于前 i 首歌曲，用前 j 张 CD 外加 k 分钟，能够容纳的最多歌曲数量。
那么最终的状态就为 f[n, m, 0]。

状态转移：

• 首先继承上一位置的状态：f[i, j, k] = f[i-1, j, k]；
• 当外加的 k 分钟大于当前歌曲大小时，就可以从 f[i-1, j, k-a[i] 来转移：f[i, j, k] = f[i-1, j, k-a[i]] + 1；
• 否则，就需要存储在上一张唱片中，从 f[i-1, j-1, t-a[i]] 来转移：f[i, j, k] = f[i-1, j-1, t-a[i]] + 1；

Code

#include<bits/stdc++.h>
using namespace std;

const int N = 210, mod = 1e9+7;
int T, n, m;
int a[N];
int f[N][N][N];

signed main(){
	int t;
	cin >> n >> t >> m;
	for(int i=1;i<=n;i++) cin >> a[i];
	
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			for(int k=0;k<=t;k++)
			{
				f[i][j][k] = f[i-1][j][k];
				if(k>=a[i]) f[i][j][k] = max(f[i][j][k], f[i-1][j][k-a[i]] + 1); 
				else if(t-a[i] >= 0 && j >= 1) f[i][j][k] = max(f[i][j][k], f[i-1][j-1][t-a[i]] + 1);
			}
		}
	}
	cout << f[n][m][0];
	
	return 0;
}
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

经验
状态定义要敢想。