CF626F 【Group Projects】

大概是稍微详细讲了讲优化部分。 考虑暴力计数，大概就是 $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\}$ 的这么一个数列。一个比较简单的方法就是： $$ a_r-a_l=\sum_{i=l+1}^r(a_i-a_{i-1}) $$ ~~一看就是老分式裂项了~~ 于是本质上只是优化了转移。令 $d=a_i-a_{i-1}$ 可以得到：  然后就没有然后了，复杂度 $O(n^2\max\{k,\max\{a_i\}\})$ 。 ```cpp #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 ; } ```