UVaLive6435（dp）

要点

题意：两个数据传输数列，每个数列里有若干个数据包并给出发出时间\(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;

}

巴特西

UVaLive6435（dp）

要点

最新文章

热门文章