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		secondtypedef 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;
}

?

　　

?