Codeforces 626F Group Projects （DP）

题目链接 8VC Venture Cup 2016 - Elimination Round

题意把$n$个物品分成若干组，每个组的代价为组内价值的极差，求所有组的代价之和不超过$k$的方案数。

考虑DP，$f[i][j][k]$表示考虑到第$i$个物品的时候，还有$j$组尚未分配完毕，当前状态总代价为$k$的方案数。

先把$a[]$升序排序，那么极差就可以转化为后面的元素减前面的元素不停叠加的效果。

当考虑第$i$个物品的时候有$4$种转移方法：

当前物品新开一组并且继续等待分配；

当前物品新开一组，并且这个物品单独当做一种；

当前物品插入到之前的$j$组中的一组中去并让这个组继续等待分配，那么有$j$种插入的方案；

当前物品插入到之前的$j$组中的一组中去并作为这个组的最大值（停止分配），同样有$j$种插入的方案。

时间复杂度$O(n^{2}k)$

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

#define MP		make_pair

#define fi		first

#define se		second

typedef long long LL;

const int N  = 202;

const int M  = 1010;

const LL mod = 1e9 + 7;

int n, m;

int a[N];

int x;

LL f[2][N][M];

LL ans;

void up(LL &x, LL y){ x = x + y; x %= mod;}

int main(){

	scanf("%d%d", &n, &m);

	rep(i, 1, n) scanf("%d", a + i);

	sort(a + 1, a + n + 1);

	a[0] = a[1];

	f[0][0][0] = 1;

	x = 1;

	rep(i, 0, n - 1){

		x ^= 1;

		memset(f[x ^ 1], 0, sizeof f[x ^ 1]);

		rep(j, 0, i){

			rep(k, 0, m) if (f[x][j][k] && k + j * (a[i + 1] - a[i]) <= m){

				int cnt = k + j * (a[i + 1] - a[i]);

				up(f[x ^ 1][j + 1][cnt], f[x][j][k]);

				up(f[x ^ 1][j][cnt], f[x][j][k]);

				if (j){

					up(f[x ^ 1][j][cnt], f[x][j][k] * j % mod);

					up(f[x ^ 1][j - 1][cnt], f[x][j][k] * j % mod);

				}

			}

		}

	}

	ans = 0;

	rep(i, 0, m) up(ans, f[x ^ 1][0][i]);

	printf("%lld\n", ans);

	return 0;

}

巴特西

Codeforces 626F Group Projects （DP）

最新文章

热门文章