题解:「CEOI2016」袋鼠 和 HDU6764 Blood Pressure Game

「CEOI2016」袋鼠

statement

一行共有 \(N\) 个格子,从左到右从 \(1\)\(N\) 编号。一只袋鼠从 \(c_s\) 出发,经过恰好 \(N - 1\) 次跳跃,到达 \(c_f\) ,并且经过所有的 \(N\) 个格子,每次跳跃的方向都与上一次不同。如果袋鼠当前所在的格子为 \(\rm current\) ,来自 \(\rm prev\) ,则其下一个格子 \(\rm next\) 满足:

  • 如果 \(\rm prev < current\),则 \(\rm next < current\)
  • 如果 \(\rm current < prev\),则 \(\rm current < next\)

求不同的跳跃方案数除以 \(10 ^ 9 + 7\) 的余数。

Hints

\(2\le N\le 2000\)\(c_s \neq c_f\) .

solution

线头 DP ...

其实就是一个求排列个数的问题,这里的排列指的就是跳跃的下标序列。

然后开始线头,设 \(f(i, j)\) 表示填了前 \(i\) 个数,产生 \(j\) 个没有接的向上的线头的方案数,转移:

\[f(i, j) = f(i - 1, j + 1) \times j\times(j + 1) + f(i - 1, j - 1) \]

其实这个转移方程就是接几个散乱的线头的过程。

对于 \(c_s\)\(c_f\) ,默认它们的线头位于最左边和最右边,然后答案就是 \(dp(n - 1, 0)\) ,因为这个时候最后一个数字的摆放位置是唯一的。

考虑这个东西为什么可以不重不漏,因为在一个排列中,每个线头可以看成一个笛卡尔树,合并相当于两颗二叉树用根节点接牢,增加一个线头可以看成新建一个节点的笛卡尔树,而笛卡尔树的形态和一个排列可以构成双射,所以保证了每次的不同。

时间复杂度 \(\mathcal O (n^2)\)

int n, s, t, dp[N][N];
int main() {
	scanf("%d%d%d", &n, &s, &t);
	dp[0][0] = 1;
	forn(i,1,n) forn(j,0,i) {
		if(i != s && i != t) {
			dp[i][j] = 1ll * dp[i - 1][j + 1] * (j + (i > s) + (i > t)) %Mod * (j + 1) %Mod;
			if(j) dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) %Mod;
		} else {
			dp[i][j] = dp[i - 1][j];
			dp[i][j] = (dp[i][j] + 1ll * dp[i - 1][j + 1] * (j + 1) %Mod) %Mod;
		}
	}
	printf("%d\n", dp[n - 1][0]);
	return 0;
}

Thinks

使用这种解决排列问题的 DP 的充要条件。

这个模型的特点:

  • 不重不漏
  • 无后效性

而且这两个特点都是基于每个小集合的笛卡尔树,所以能使用这个东西的时候,序列中的数不一定是排列,但是要保证不同序列都只能对应一颗笛卡尔树,所以序列中的数字必须两两不同,并且枚举的时候从小到大或从大到小。

HDU6764 Blood Pressure Game

statement

给一个长度为 \(n\) 的数组 \(a\),定义一个数组的权值为

\[\sum_{i = 1} ^ {n - 1} |a_{i + 1} - a_i| \]

求在 \(a\) 的每一种排列中,权值严格前 \(k\) 大方案的权值,以及每种方案的方案数,方案数对 \(10 ^ 9 + 7\) 取模。

Hints

\(n\le 600\)\(k\le 20\) , 数组 \(a\) 中整数大小互不相同 .

solution

套路地把贡献拆成排序后的数组 \(a\) ,数 \(|a_{i + 1} - a_i|\) 的个数。

由于元素互不相同,采用上述模型,设 \(dp(i, j, k)\) 表示从小到大加入了前面 \(i\) 个数,构成的集合个数为 \(j\) ,是否确定首尾的状态。

其中 \(k = 0\) 表示没有确定首或尾,\(k = 1\) 表示确定了首尾中的一个,\(k = 2\) 表示首尾全部确定了。

由于要记录前 \(k\) 大,所以每个状态除了计数,还要记录转移后序列的每一种权值的集合。

初始状态 \(dp(1, 1, 0)\)\(dp(1, 1, 1)\)

首先是权值的转移,发现从 \(dp(i,,)\rightarrow dp(i + 1,,)\) 的贡献是相同的,都是 \((a_i - a_{i - 1}) \times (2j - k)\)

因为有 \(j - k\) 个集合需要连左边和右边,\(k\) 个集合只需要接一边,加之每次加入的都是比当前元素大的元素,这样的过程自动完成了一个差分的前缀和。

对于每种集合的构造,一定不能破坏上述的权值计算的过程,所以,确定为首尾的集合只能在一边进行构造,不能在另一边构造,这会影响到对于方案数转移的过程。

分类讨论方案数的转移:

  • 新建一个集合,不作为首尾,\(dp(i + 1, j + 1, k)\leftarrow dp(i, j, k)\) ,方案数为 \(j - k + 1\)
  • 新建一个集合,作为首尾,\(dp(i + 1, j + 1, k + 1)\leftarrow dp(i, j, k)\) ,方案数为 \(2 - k\) .
  • 合并两个集合,\(dp(i + 1, j - 1, k)\leftarrow dp(i, j, k)\) ,因为求最大权值的特殊性,集合在序列中的排列顺序已经确定,方案数为 \(j - 1\) .
  • 新建一个集合,并且在这一轮就与另一个集合合并,不作为最后的 \(a_1\)\(a_n\)\(dp(i + 1, j, k)\leftarrow dp(i, j, k)\) ,方案数为 \(2j - k\) .
  • 新建一个集合,并且在这一轮就作为 \(a_1\)\(a_n\) ,与其他集合合并,\(dp(i + 1, j, k + 1) \leftarrow dp(i, j, k)\) ,方案数为 \(2 - k\) .

实现的时候,对于每种状态都记录前 \(k\) 最大权值的方案,每种方案记为二元组 \((val, num)\) ,分别为这种排列的权值以及对应的方案数。

对于每个状态记录的二元组对于关键字 \(val\) 先排序,记录前 \(k\) 个后,再进行转移。

时间复杂度 \(\mathcal O (n ^ 2 k\log k)\)

int n, m; i64 a[N];
struct state {
	node U[M * 5]; int num;
	state() {num = 0;}
	inline void reset() {num = 0;}
	inline void ins(i64 val, Mint t) {U[++num] = node(val, t);}
	inline void init() {
		sort(U + 1, U + num + 1);
		int sem = 0;
		forn(l,1,num) {
			int r = l; Mint sum = U[l].num;
			while(r < num && U[r + 1].val == U[l].val) sum += U[++r].num;
			U[++sem] = node(U[l].val, sum);
			l = r;
		}
		num = min(m, sem);
	}
} dp[3][2][N];
inline void solve() {
	scanf("%d%d", &n, &m);
	forn(i,1,n) scanf("%lld", a + i);
	sort(a + 1, a + n + 1);
	dp[0][1][1].ins(0, Mint(1)), dp[1][1][1].ins(0, Mint(2));
	int now = 1;
	rep(i,1,n) {
		forn(j,1,n) rep(k,0,3) if(dp[k][now][j].num) {
			dp[k][now][j].init(); 
			forn(t,1,dp[k][now][j].num) {
				i64 val = dp[k][now][j].U[t].val + (a[i + 1] - a[i]) * (2 * j - k);
				Mint num = dp[k][now][j].U[t].num; 
				if(j - k + 1 > 0) dp[k][now ^ 1][j + 1].ins(val, num * Mint(j - k + 1));
				if(2 * j - k > 0) dp[k][now ^ 1][j].ins(val, num * Mint(2 * j - k));
				if(j > 1) dp[k][now ^ 1][j - 1].ins(val, num * Mint(j - 1));
				if(k < 2) {
					dp[k + 1][now ^ 1][j].ins(val, num * Mint(2 - k));
					dp[k + 1][now ^ 1][j + 1].ins(val, num * Mint(2 - k));
				}
			}
			dp[k][now][j].reset();
		}
		now ^= 1;
	}
	dp[2][now][1].init();
	forn(i,1,min(m, dp[2][now][1].num)) printf("%lld %d\n", dp[2][now][1].U[i].val, dp[2][now][1].U[i].num.res);
	forn(i,1,m - dp[2][now][1].num) puts("-1");
	forn(j,1,n) rep(k,0,3) if(dp[k][now][j].num) dp[k][now][j].reset();
}

题解:「CEOI2016」袋鼠 和 HDU6764 Blood Pressure Game

上一篇:第一章 数字油气田系统简介(4)


下一篇:nacos下载安装