CF1810G 题解

First Post:

Last Update:

一道思路有启发意义的 DP 题，考察状态设计的优化。

首先一个 的做法比较好想，枚举最大前缀和 ，在第一个 的地方统计每个序列的答案。这需要使用 算出在序列第 项， 且前面的 均不大于 的方案数，故时间复杂度为立方。

考虑平方怎么做。注意到这个 在转移中唯一的限制就是 ，我们却需要在 DP 中枚举 和 这两个维度，这看上去很浪费信息。我们把 变形为 ，那我们在 DP 中就只需要记录 和 这两维了。

重写 DP 状态， 表示目前 DP 到第 位， 的方案数。但这会迎来两个问题。

第一个问题：这个 要在哪里乘？实际上，在 的时候， 一定等于 ，所以在赋初值的时候，直接令 即可。

第二个问题：如何统计答案？我们只需多记录一维 ，表示在前面的转移过程中， 是否等于过 ，最后统计答案时，把所有 相加即可。（这个技巧类似于 AGC013D，但不完全相同）。

综上，我们以 时间复杂度解决了本题。

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 <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5,P = 1e9 + 7;
inline int qpow(int a,int b) { int res = 1;while(b) {if(b&1) res = 1ll * res * a % P;a = 1ll * a * a % P;b >>= 1;} return res;}
int n;
int h[N];
int f[N][N][2];
int p[N];
int ans[N];
inline void work()
{
	scanf("%d",&n);
	for(int i = 1;i <= n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		p[i] = 1ll * x * qpow(y,P - 2) % P;
	}
	for(int i = 0;i <= n;i++) scanf("%d",&h[i]);
	for(int i = 0;i <= n;i++)
		for(int j = 0;j <= n;j++)
			f[i][j][0] = f[i][j][1] = 0;
	for(int i = 0;i <= n;i++)
	{
		if(i == 0) f[0][0][1] = h[i];
		else f[0][i][0] = h[i];
	}
	for(int i = 1;i <= n;i++)
		for(int j = 0;j <= n;j++)
		{
			if(j != 0)
			{
				f[i][j][0] = (1ll * f[i - 1][j + 1][0] * p[i] % P + 1ll * f[i - 1][j - 1][0] * (P + 1 - p[i]) % P) % P;
				f[i][j][1] = (1ll * f[i - 1][j + 1][1] * p[i] % P + 1ll * f[i - 1][j - 1][1] * (P + 1 - p[i]) % P) % P;
			}
			else 
				f[i][j][1] = (1ll * (f[i - 1][j + 1][0] + f[i - 1][j + 1][1]) * p[i] % P + 1ll * (f[i - 1][j - 1][0] + f[i - 1][j - 1][1]) * (P + 1 - p[i]) % P) % P;
		}
	for(int i = 1;i <= n;i++)
	{
		ans[i] = 0;
		for(int j = 0;j <= n;j++)
			(ans[i] += f[i][j][1]) %= P;
	}
	for(int i = 1;i <= n;i++) 
		printf("%d ",ans[i]);
	printf("\n");
}
int main()
{
	int T;
	cin >> T;
	while(T--) work();
	return 0;
}
≡