[APIO2016]划艇

发表于

link

难度

思维难度 : 三星
代码难度 ：二星

标签

dpdp + 离散化离散化 + 计数

思路

考虑最最朴素的 dpdp ， 设 f[i][j]f[i][j] 表示 dpdp 到第 ii 所学校，第 ii 所学校参加，最大值为 jj , 那么显然有 f[i][j]=∑p=0i−1∑k=0j−1f[p][k]（ai≤j≤bi）f[i][j] = \sum_{p = 0}^{i-1}\sum_{k = 0}^{j - 1}f[p][k] （ a_i \leq j \leq b_i） ， 用前缀和优化可以做到 O(n2max⁡(bi))O(n^2\max(b_i)) 不能接受.

考虑优化掉 max⁡(bi)\max(b_i) ， 把 aia_i 和 bib_i 离散化 , 这样可以优化到 O(n3)O(n^3) ， 但是又有一个问题， f[i][j]f[i][j] 的意义会变为 dpdp 到第 ii 所学校，第 ii 所学校参加，最大值所在区间为 jj . 可以想到一种 dpdp.

f[i][j]=∑p=0i−1∑k=0j−1(rj−lj+1)f[p][k]f[i][j] = \sum_{p = 0}^{i-1}\sum_{k = 0}^{j - 1}(r_j - l_j + 1)f[p][k] ，

然而这样是不对的，因为没有考虑 pp 到 jj 之间有些数也可以在区间 jj 中. 所以方程应该是 f[i][j]=∑p=0i−1∑k=0j−1g(lj,rj,num(p+1,i,j))f[p][k]f[i][j] = \sum_{p = 0}^{i-1}\sum_{k = 0}^{j - 1} g(l_j, r_j, num(p + 1, i, j)) f[p][k]

num(i,j,x)num(i, j, x) 表示从 ii 到 jj 包含区间 xx 的数的数量.

g(l,r,x)g(l, r, x) 表示从区间 [0,0]+[l,r][0,0] + [l, r] 中取 xx 个数，第 xx 个数非零 , 要求所有非零数严格递增的方案数. 这显然是 (r−l+xx)\tbinom{r - l + x}{x} ， 证明如下:

枚举哪几个数选 00 , 让其它的数递增。那么方案数为

∑i=0x(xi)(r−l+1x−i)−∑i=0x−1(x−1i)(r−l+1x−i−1)减去最后一个数为0的方案=(r−l+1+xx)−(r−l+xx−1)=(r−l+xx)\begin{aligned} &\quad\sum_{i=0}^{x} \tbinom{x}{i}\tbinom{r - l + 1}{x - i} - \sum_{i=0}^{x - 1} \tbinom{x-1}{i} \tbinom{r-l+1}{x-i - 1} \quad 减去最后一个数为 0 的方案\\ &=\tbinom{r-l+1+x}{x}-\tbinom{r - l + x}{x-1}\\ &=\tbinom{r-l+x}{x} \end{aligned}

所以 f[i][j]=∑p=0i−1∑k=0j−1(r−l+xx)f[p][k]f[i][j] = \sum_{p = 0}^{i-1}\sum_{k = 0}^{j - 1} \tbinom{r-l+x}{x} f[p][k]

前缀和可以优化到 O(n3)O(n^3)

Code

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long

using namespace std;

const int N = 3e3 + 10, mod = 1e9 + 7;
int n;
int C[N], a[N], b[N], tmp[N];
int f[N][N], g[N][N];
int inv[N];

int main() {
    scanf("%d", &n);
    inv[1] = 1;
    for (int i = 2; i <= n; ++i) {
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
    }
    int tot = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &a[i], &b[i]);
        ++b[i];
        tmp[++tot] = a[i], tmp[++tot] = b[i];
    }
    sort(tmp + 1, tmp + tot + 1);
    tot = unique(tmp + 1, tmp + tot + 1) - tmp - 1;
    for (int i = 1; i <= n; ++i) {
        a[i] = lower_bound(tmp + 1, tmp + tot + 1, a[i]) - tmp;
        b[i] = lower_bound(tmp + 1, tmp + tot + 1, b[i]) - tmp;
    }
    C[0] = 1;
    for (int i = 0; i < tot; ++i) g[0][i] = 1;
    int ans = 0;
    for (int j = 1; j < tot; ++j) {
        int L = tmp[j + 1] - tmp[j];
        for (int i = 1; i <= n; ++i) C[i] = 1ll * C[i - 1] * (L - 1 + i) % mod * inv[i] % mod;
        for (int i = 1; i <= n; ++i) {
            if (a[i] <= j && j + 1 <= b[i]) {
                int m = 1;
                for (int k = i - 1; ~k; --k) {
                    f[i][j] = (f[i][j] + 1ll * g[k][j - 1] * C[m] % mod) % mod;
                    if (a[k] <= j && j + 1 <= b[k]) ++m;
                }
            }
            g[i][j] = 0;
            for (int k = 1; k <= j; ++k) (g[i][j] += f[i][k]) %= mod;
            ans += f[i][j];
            ans %= mod;
        }
    }
    cout << ans << endl;
    return 0;
}

总结

当 dpdp 中涉及较大的值域时，可以考虑离散化后进行 dpdp ，在 dpdp 时要注意很多细节。如要考虑之前和现在选的数在同一区间的情况.