【题解】[CF626F]Group Projects

有 $n$ 个学生,每个学生有一个能力值 $a_i$。现在要把这些学生分成一些(任意数量的)组,每一组的“不和谐度”是该组能力值最大的学生与能力值最小的学生的能力值的差。求所有不和谐度之和不超过 $k$ 的分组方案总数对 $10^9+7$ 取模。

$n\leq 200,k\leq 1000,0\leq a_i\leq 500$

从头开始的计数生活.png

考虑暴力计数,大概就是 $f_{i,j,k}$ 表示考虑了前 $i$ 个学生,分了 $j$ 组,当前不和谐度总和为 $k$ 的方案数。发现这样没法转移,因为并不知道该怎么考虑插入一个元素时的贡献。考虑对于一种状态,如果钦定了其中某些集合的最大值或者最小值已经固定,如果当前元素超过了这个 bond,就不能再用当前元素更新。于是考虑另一种状态,$f_{i,j,k}$ 表示考虑了前 $i$ 个学生,分了不知道组,但是有 $j$ 组的最大值还没确定,当前不和谐度总和为 $k$ 的方案数 。这样显然是需要将所有权值排序之后再 $dp$ 的。

考虑转移。每次遇到一个新的元素,可以将其和之前的某一组合并,或者单独新开一组。记没确定最大值的集合为「未闭合集合」,那么就有四种情况:

1、合并,但是那个集合仍未闭合。

2、合并,那个集合闭合了。

3、不合并,新开的集合未闭合。

4、不合并,新开的集合闭合了。

于是转移就是

分别对应四种情况。

考虑这么做的复杂度,似乎是 $O(n^2k)$ ,但是由于中间转移过程的第三维可能会到 $\pm 10^4$ ,大小无法准确预估,所以时空复杂度都是 $O(n^2\sum a_i)$ 的。于是就 gg 。

考虑稍微抽象一下,每个集合的 $min/max$ 可以看做在一条值域轴上线段的左、右端点,对于每个时刻 $i$ ,未闭合的集合就是某些会被 $i$ 横切掉的线段。那么对于某条直线 $(l,r)$ ,满足 $l<i<r$ ,在第 $i$ 个时刻,记录的是代价是 $-a_l$,但这种方法并不聪明,因为只有当取到 $r$ 时,$-a_l$ 才会被用上,所以对于任意一个 $i,l<i<r$ 而言,$-a_l$ 都是没必要承载的空间。于是考虑怎么将一条线段的贡献平摊到每个点上,这样每一维转移就不再是 $O(\max\{\sum a_i,k\})$ 而是 $O(\max\{a_i,k\})$ 。

考虑平摊的话,即如何将 $a_r-a_l$ 展开成每一项都 $<\max\{a_i,k\}$ 的这么一个数列。一个比较简单的方法就是:

一看就是老分式裂项了

于是本质上只是优化了转移。令 $d=a_i-a_{i-1}$ 可以得到:

然后就没有然后了,复杂度 $O(n^2\max\{k,\max\{a_i\}\})$ 。

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
28
29
30
31
32
#define MAXN 510
#define MAXK 1010
#define Mod 1000000007

using namespace std ;
LL dp[2][MAXN][MAXK], ans ;
int N, K, M, base[MAXN], dif[MAXN] ;

il void del(int &x, const int &y){ x -= y ; if (x < 0) x += Mod ; }
il void add(LL &x, const LL &y){ x += y ; if (x > Mod) x %= Mod ; }
int main(){
cin >> N >> K ; int i, j, k, d ;
for (i = 1 ; i <= N ; ++ i) scanf("%d", &base[i]) ;
sort(base + 1, base + N + 1), dp[0][1][0] = dp[0][0][0] = 1 ;
for (i = 1 ; i < N ; ++ i) dif[i] = base[i + 1] - base[i] ;
for (d = i = 1 ; i < N ; ++ i, d ^= 1){
int o = d ^ 1 ;
for (j = 0 ; j <= N ; ++ j){
int op = dif[i] * j ;
for (k = 0 ; k <= K ; ++ k){
int val = k + op ;
LL res = dp[o][j][k], v = res * j % Mod ;
dp[o][j][k] = 0 ; if (val > K) continue ;
if (j) add(dp[d][j - 1][val], v) ;
add(dp[d][j][val], v + res), add(dp[d][j + 1][val], res) ;
}
}
}
for (i = 0 ; i <= K ; ++ i)
add(ans, dp[(N - 1) & 1][0][i]) ;
cout << ans << endl ; return 0 ;
}