CF626FGroup Projects

妙啊

一开始我以为是按照顺序分组,这不简单?,我直接dp就能很简单的做完

第二个样例都过不去,再一看题发现是随意分组....

像这样随意分组的计数和排列方案计数没区别,总要给你计算代价的时候简单一点吧...比如之前那个sdoi就是相邻最大值有关,因此可以很愉快的记录组数就行了

本题也是一样,按照权值排序之后,每一组的代价之和两个端点有关,也就是说我们可以不断开新组,每次开一个新组代价都是w,然后同时我们可以添加一个右端点封死一组,代价是v,我们要保证最后代价和小于k,因此记录当前代价和就好了

不现实,因此我们要记录减掉了多少,这个上界是 $\sum a_i$

因此我们可以把权值差分,最大值减去最小值像什么?是不是像前缀和数组对应区间和的计算方法啊?

用小花的话说就是把直线的代价均摊给每个数,从而你会发现每个数都是大于0的!

此时我们的转移方程就改了一点点而已,仔细想想就能改过来了

复杂度 $O(n^2k)$

#include<bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7;
const int MAXN = 205;
const int MAXK = 1e3 + 7;

int n, k, a[MAXN], f[MAXN][MAXK], g[MAXN][MAXK], d[MAXN], M; //滚动一维吧
inline int add(int x, int y ) {
	x += y;
	if(x >= P)x -= P;
	return x;
}

int main() {
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	sort(a + 1, a + n + 1);
	g[0][0] = 1;
	for(int i = 1; i <= n; ++i) {
		d[i] = a[i] - a[i - 1];
		for(int j = 0; j <= k; ++j) {
			for(int l = i; l >= 0; --l) {
				if(j >= l * d[i])
					f[l][j] = add(f[l][j], 1ll * g[l][j - l * d[i]] * l % P);
				if(j >= (l + 1)*d[i] && l < i)
					f[l][j] = add(f[l][j], 1ll * (l + 1) * g[l + 1][j - (l + 1) * d[i]] % P);
				if(j >= (l - 1)*d[i] && l)
					f[l][j] = add(f[l][j], g[l - 1][j - (l - 1) * d[i]]);
				if(j >= l * d[i])
					f[l][j] = add(f[l][j], g[l][j - l * d[i]]);
			}
		}
		for(int j = 0; j <= k; ++j) {
			for(int l = i; l >= 0; --l) {
				g[l][j] = f[l][j];
				f[l][j] = 0;
			}
		}
	}
	int ans = 0;
	for(int j = 0; j <= k; ++j)
		ans = add(ans, g[0][j]);
	printf("%d\n", ans);
	return 0;
}
/*
5 222
58 369 477 58 90
*/

夏晓光(loveJY)的博客

20ZRDay7