Loj 2743 摩天大楼

Posted on | Edited on | Views:

dp 计数问题.

考虑将所有 $A_i$ 从小到大排序,依次插入到序列中,并对合法的方案数计数.

设 $dp(i,j,k,h)$ 表示插入了前 $i$ 个数,分成了 $j$ 段,已确定的元素差值之和为 $k$ ,即下图中 $y=A_i$ 直线下方部分长度,已经钦定了 $h$ 个左右边界 $(0\le h\le 2)$ 的方案数.

转移加入 $A_{i+1}$ 时,除了边界外,每段的两端都会多出 $(A_{i+1}-A_i)$ 的长度,即 $k$ 的增量为 $(A_{i+1}-A_i)\cdot (2j-h)$ .

再讨论一下 $A_{i+1}$ 插入到两端还是某段中,是否会新建一段,是否钦定为边界这些情况转移,时间复杂度 $O(n^2L)$ .

可以把第一维滚动掉来优化空间.

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
const int P = 1e9 + 7;
int add(int a, int b)
{
	return a + b >= P ? a + b - P : a + b;
}
void inc(int &a, int b)
{
	a = add(a, b);
}
int mul(int a, int b)
{
	return 1LL * a * b % P;
}
const int N = 100 + 10, M = 1000 + 10;
int n, L, a[N], dp[2][N][M][3];
void trans(int i, int id, int j, int k, int h)
{
	int val = dp[id ^ 1][j][k][h];
	int w = k + (a[i] - a[i - 1]) * (2 * j - h);
	if (w > L)
		return;
	inc(dp[id][j + 1][w][h], mul(j + 1 - h, val));
	if (j)
		inc(dp[id][j - 1][w][h], mul(j - 1, val));
	inc(dp[id][j][w][h], mul(j * 2 - h, val));
	if (h < 2)
	{
		if (j)
			inc(dp[id][j][w][h + 1], mul(2 - h, val));
		inc(dp[id][j + 1][w][h + 1], mul(2 - h, val));
	}
}
int main()
{
	n = read(), L = read();
	if (n == 1)
		return puts("1"), 0;
	for (int i = 1; i <= n; ++i)
		a[i] = read();
	sort(a + 1, a + 1 + n);
	int id = 0;
	dp[id][0][0][0] = 1;
	for (int i = 1; i <= n; ++i)
	{
		id ^= 1;
		memset(dp[id], 0, sizeof dp[id]);
		for (int j = 0; j <= i; ++j)
			for (int k = 0; k <= L; ++k)
				for (int h = 0; h <= 2; ++h)
					if (dp[id ^ 1][j][k][h])
						trans(i, id, j, k, h);
	}
	int ans = 0;
	for (int k = 0; k <= L; ++k)
		inc(ans, dp[id][1][k][2]);
	printf("%d\n", ans);
	return 0;
}