这个题我可能想复杂了

$w[l][r]$为$[l,r]$这个区间内一个背包可以装的最大数量，这个东西显然可以用反贪弄

这样我们的题目就变为选择$m$个区间使得权值最大

考虑$dp$

$f[i][j]$为前$i$个数中一定要选$i$这个点的前提下选$j$段的最大值

$f[i][j] = max(f[i-1][j],f[k][j-1]+w[k+1][i])$

其中 $0 <= k < i$

然后就做完了

code

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

const int N = 1e3 + 10;

int n, k, m, a[N], w[N][N], f[N][N];

void read() {
	cin >> n >> k >> m;
	for(int i = 1; i <= n; i++) cin >> a[i];
}

priority_queue<int> q;

void compute() {
	for(int l = 1; l <= n; l++) {
		int now = 0;
		for(int r = l; r <= n; r++) {
			if(now + a[r] <= k) {
				now += a[r];
				q.push(a[r]);
			} else {
				if(q.size() && a[r] < q.top()) {
					now -= q.top();
					q.pop();
					now += a[r];
					q.push(a[r]);
				}
			}
			w[l][r] = q.size();
		}
		while(q.size()) q.pop();
	}
	for(int i = 1; i <= n; i++) {
		for(int p = 1; p <= m; p++) {
			for(int j = 0; j < i; j++) {
				f[i][p] = max(max(f[i-1][p],f[j][p-1]+w[j+1][i]),f[i][p]);
			}
		}
	}
	cout << f[n][m];
}

int main() {
	read();
	compute();
	return 0;
}

警钟

用优先队列时，一定要注意判断队里面有没有元素！！！不然会RE

背包问题

设 f[i][j] 表示前 i 个背包，第 i 个背包载重量为 j，最多装入的物品数量

则 ans = f[n][C]

按物品编号从小到大依次考虑

对于当前物品，当前背包 i

（1）不放

（2）放（肯定放在当前背包 i 中，前提是能放得进去）

f[i][j] = max(f[i-1][C], f[i][j-a[i]])+1

f[i-1][C] 表示启用背包 i，将当前物品作为第一个放进背包 i 的物品

f[i][j-a[i]] 表示背包 i 已经装入其他物品了，继续将当前物品放进背包 i 中