UVaLive6435（dp）

佚名 6年前 (2019-05-04) 随笔 783人围观抢沙发百度已收录

要点

题意：两个数据传输数列，每个数列里有若干个数据包并给出发出时间\(t\)，每个数据包到达的时间\(T\)是\(t <= T < t + D\)，问有多少种到达序列。
将题目转化为第二个数列插入第一个数列。用第一个数列将时间点划分为\(N+1\)个部分，对于第二数列的每个数据包，预处理它左右范围，即这\(N+1\)个空，它可以插入哪些空。
\(i\)为第二个数列的第\(i\)个，\(j\)为第一个数列的\(j-1\)和\(j\)的中间空，\(dp[i][j]\)表示把\(i\)插到\(j\)空里的方案数，转移即是保证\(i-1\)在\(i\)的前面某一空即可。

#include <cstdio>
#include <vector>
using std::vector;

typedef long long ll;
const int maxn = 5e4 + 5;
const int mod = 1e9 + 9;
int T, N, M, D;
int a[maxn], b[maxn];
ll dp[maxn][205];
vector<int> v[maxn];

int main() {
    scanf("%d", &T);
    for (int kase = 1; kase <= T; kase++) {
        scanf("%d %d %d", &N, &M, &D);
        for (int i = 1; i <= N; i++)
            scanf("%d", &a[i]);
        for (int i = 1; i <= M; i++)
            scanf("%d", &b[i]);

        for (int p = 1, i = 1; i <= M; i++) {
            v[i].clear();
            for (; p <= N && a[p] + D <= b[i]; p++);
            for (; p <= N && b[i] + D > a[p]; p++)
                v[i].push_back(p);
            v[i].push_back(p), p = v[i][0];//p:1~n+1
        }

        for (int j = 0; j < v[1].size(); j++)
            dp[1][j] = 1;
        for (int i = 2; i <= M; i++) {
            int p = 0;
            ll sum = 0LL;
            for (int j = 0; j < v[i].size(); j++) {
                for (; p < v[i - 1].size() && v[i - 1][p] <= v[i][j]; p++)
                    sum = (sum + dp[i - 1][p]) % mod;
                dp[i][j] = sum;
            }
        }

        ll ans = 0LL;
        for (int j = 0; j < v[M].size(); j++)
            ans = (ans + dp[M][j]) % mod;
        printf("Case #%d: %lld\n", kase, ans);
    }
    return 0;
}