经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C++ » 查看文章
预设型 DP
来源:cnblogs  作者:HANGRY_Sol&Cekas  时间:2024/8/26 9:18:35  对本文有异议

预设型 DP

《美好的一天》--青春学概论
? ? ?? ?? ?? ??
沉醉于一杯酒
???? ??? ??
带着沙哑的嗓音
? ? ?? ?? ?? ??
入睡前饮下第二杯让心情愉悦
? ? ?? ??? ??
陷入不可预知的世界
? ? ? ? ? ?? ??
又沉醉于第三杯第四杯
??? ???? ???
这个世界还有酒醉的人们
?? ??? ?? ??
再一次变得心情愉悦
? ??? ???
大家放声高歌
???????
啦~
???????
啦~
???????
啦~
???? ??
再次高歌
???????
啦~
???????
啦~
???????
啦~
??? ???
说实话
?? ? ???
我们的关系
??? ???
似友情却非友情
?? ??
偶尔会觉得
?? ?? ??
你很美丽
?? ?? ?
这像话吗
?? ?? ??
特别是在今天
??? ???
这样的日子
?? ?? ????
你现在正在
?? ???
看的镜子
?? ? ?????? ??
如果是我的脸就好了
?? ? ?? ??
有着这样不像话的想法
? ???? ?? ?? ??
会有一天我能叫你亲爱的吗
??? ?? ?? ? ?? ?
会是什么时候呢 对不起我好像喝醉了
??? ?? ????
即使这样也是好日子
? ? ??? ????
应该没有关系吧
? ? ?? ?????
饮下一杯酒
? ? ?? ? ???
第二杯已经到了凌晨三点
??? ?? ? ???
没关系 直到清晨来临
?? ?? ??
我会一直
? ??
在你左右
?? ? ?? ?? ??
熬夜饮下的酒
?? ????? ??
即使会让第二天眩晕
??? ?? ? ???
没关系 靠在我的肩膀上
? ?????
我会像影子般
??? ?? ? ??
默默无语 一直陪伴你身边
? ? ? ? ? ?? ??
又沉醉于第三杯第四杯
??? ???? ???
这个世界还有酒醉的人
?? ??? ?? ??
再一次变得心情愉悦
? ??? ???
大家放声高歌
???????
啦~
???????
啦~
???????
啦~
???? ??
再次高歌
???????
啦~
???????
啦~
???????
啦~
??? ???? ?
你是今天的主角
?? ???
生日快乐
??? ? ??? ?
也祝贺你
??? ???
近在眼前的入伍日子
??? ? ??
不是开玩笑
?? ? ??? ?
我也马上就要去了
?? ?? ?? ??
不要想太多 小子
? ??? ??
将空杯斟满酒
? ?? ?? ?? ???
你不是一直想要成为
?? ???
真正的男人吗
?? ? ??? ? ??
现在这一天来了
?? ?? ?? ?? ??
我独一无二的朋友
???? ???
你也是一样
??? ?????
今天我们要
??? ?? ???
一直喝到最后
? ? ?? ?????
饮下一杯酒
? ? ?? ? ???
第二杯已经到了凌晨三点
??? ?? ??
我们正年轻
? ??? ??
这个深夜太长
?? ??? ???
仅有的担心是
?? ?? ???? ??
你已经微微醉了
?? ? ?? ?? ??
熬夜饮下的酒
?? ????? ??
即使会让第二天眩晕
??? ?? ??
我们正年轻
?? ????
那就是祝福
? ??? ???
这是为我们
?? ???
唱的歌
??? ?? ??
在我的世界沉醉旋转
? ? ?? ???
闭上我的双眼
?? ?? ?? ?????
虽然醉酒让我有些眩晕
? ??? ? ??
但我喜欢这样的心情
?? ???? ?
想起你的夜里
?? ?? ??? ???
我再一次歌唱
???????
啦~
???????
啦~
???????
啦~
???? ??
再次高歌
???????
啦~
???????
啦~
???????
啦~
???? ?? ??? ??
再次高歌 就算跑调
??? ? ??? ???
没关系 一点也不奇怪
?????
今天这样的日子
?? ??? ? ????
即使让我看到你晚上吃的什么
???? ???
也没关系
?????
今夜
?? ?? ??
回家的路
??? ?? ?? ???
就算跳舞也没关系
?????
像今天
?? ???
在一起的日子
?? ????? ?? ?? ?
和美好的人一起度过的让人心情愉悦的日子
?????
今天这样
? ? ?? ?? ?? ??
沉醉于一杯酒
???? ??? ??
带着沙哑的嗓音
? ? ?? ?? ?? ??
入睡前饮下第二杯让心情愉悦
? ??? ???
大家放声高歌

前言

一种非常神奇的 \(DP\) 方式,可以处理排列计数问题。

例题

DP 搬运工1

题意:给你 \(n,K\) ,求有多少个 \(1\)\(n\) 的排列,满足相邻两个数的 \(\max\) 的和不超过 \(K\) 。答案对 \(998244353\) 取模。

\(n \le 50 , K \le n^2\)

\(dp_{i , j , k}\) 表示 前 \(i\) 个数,分成 \(j\) 个连续段,和为 \(k\) 的个数。

我们从大往小里加,保证了每次增加的答案为 \(i\) .

无非分成三种情况:

  1. \(i\) 自成一个连续段 : 现在有 \(j - 1\) 个连续段,新加的有 \(j\) 种可能性,因此:

\[dp_{i , j , k} += dp_{i - 1 , j - 1 , k - i} \times j \]

  1. \(i\) 并在一个连续段里,即变为一个连续段的两端。 \(j\) 个连续段,显然有 \(2j\) 种选法,因此:

\[dp_{i , j , k} += dp_{i - 1 , j , k - i} \times 2j \]

  1. \(i\) 连起来两个连续段,最后 \(j\) 段,之前就是 \(j + 1\) 段,那么就是 \(j\) 个空,因此:

\[dp_{i , j , k} += dp_{i - 1 , j + 1 , k - 2i} \times j \]

于是我们就得到了 \(dp_{i , j , k}\) .

TexCode

CODE
#include <bits/stdc++.h>
#ifdef Using_Fread
char buf[1 << 20] , *p1 , *p2 ; 
#define getchar() ((p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , 1 << 20 , stdin) , p1 == p2)) ? EOF : *p1 ++)
#endif
#ifdef linux
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
using namespace std ; 
typedef long long ll ; 
const int N = 52 ; 
const int mod = 998244353 ; 
namespace Fast_IO {
	inline ll read() {
		ll x = 0 , f = 1 ; 
		char c = getchar() ; 

		while (c < '0' || c > '9') {
			c = getchar() ; 
		}

		while (c >= '0' && c <= '9') {
			x = x * 10 + c - '0' ; 
			c = getchar() ; 
		}

		return x * f ; 
	}
	void write(ll x) {
		if (x / 10) write(x / 10) ; 
		putchar(x % 10 + '0') ; 
	}
} using namespace Fast_IO ; 

int n , K ; 
int dp[N][N][N * N] ; 

signed main() {
	#ifdef LOCAL
	freopen("1.in" , "r" , stdin) ; 
	freopen("1.out" , "w" , stdout) ; 
	#endif
	n = read() , K = read() ; 
	if (n == 1) {
		cout << 1 ; 
		return 0 ; 
	}
	dp[1][1][0] = 1 ; ll val = 1 ; 

	for (int i = 2 ; i <= n ; ++ i) {
		dp[i][i][0] = (val * i) % mod ; val = (val * i) % mod ; 

		for (int j = 1 ; j < i ; ++ j) {
			for (int k = 1 ; k <= i * i ; ++ k) {
				dp[i][j][k] = ((ll)dp[i - 1][j - 1][k] * (ll)j) % mod ; 
				dp[i][j][k] = (dp[i][j][k] + (dp[i - 1][j][k - i] * ((2ll * (ll)j) % mod)) % mod) % mod ; 

				if (k >= 2 * i) dp[i][j][k] = (dp[i][j][k] + (ll)((ll)dp[i - 1][j + 1][k - 2 * i] * (ll)j) % mod) % mod ; 
			}
		}
	}

	ll ans = 0 ; 
	for (int i = 1 ; i <= K ; ++ i) {
		ans = (dp[n][1][i] + ans) % mod ; 
	}

	cout << ans << '\n' ; 
}

[JOI Open 2016] 摩天大楼

译自 JOI Open 2016 T3 「高層ビル街 / Skyscraper」

题目描述

将互不相同的 \(N\) 个整数 \(A_1, A_2, \cdots, A_N\) 按照一定顺序排列。

假设排列为 \(f_1, f_2, \cdots, f_N\),要求:\(| f_1 - f_2| + | f_2 - f_3| + \cdots + | f_{N-1} - f_N| \leq L\)

求满足题意的排列的方案数对 \(10^9+7\) 取模后的结果。

\(N \le 100 , L \le 1000 , A_i \le 1000 (i \in [1 , n])\)

这是好题

先考虑一下 \(O(n^2\sum\limits a_i)\) 的做法:

我们为了处理掉绝对值号,直接将 \(A_i\) 从大到小排序。

如果我们不进行连续段合并,就是说只考虑往两端加的情况,显然是一个钩子状的。

图:

(反正类似吧)

然后我们对于这样的段来说,其答案显然为 \(left + right - 2mid\)

( \(left\) 指最左端值, \(right\) 指最右段值, \(mid\) 指中间段最小的那个数 )

然后如果两个钩子合并的话,图:

我们就发现中间那个最高的变成左右两个的左端或右端。

那总答案 \(\Delta\)\(2new - left_{right} - right_{left}\)

我们发现只要不是最左端或最右端,那么都会经历一个这样的过程,因此在我们 \(DP\) 的时候,只将区间最左和区间最右的特殊考虑。

具体的,设 \(dp_{i , j , k , d}\) 表示前 \(i\) 个, \(j\) 段 , 答案为 \(k\) , 拥有 \(d\) 个端点( \(1\)\(n\) )。

那如果是合并段:

\[dp_{i , j , k , d} = dp_{i - 1 , j + 1 , k - 2a_i , d} \times j \]

至于为什么从 \(k-2a_i\) 转移来,就是为了上图中可能的减法(我们不知道那俩数是啥)准备的,非极端点不加入转移。

若是新加段且不为端点:

\[dp_{i , j , k , d} = dp_{i - 1 , j - 1 , k + 2a_i , d} \times j \]

\(a_i\) 将是 \(a_i\) 所在钩子的最小值, (上面不是算出 \(-2mid\) 吗)。

若是新加段并是端点:

\[dp_{i , j , k , d} = dp_{i - 1 , j - 1 , k + a_i , d - 1} \times(2 - d + 1) \]

端点只有左右两种情况了吧。为什么从 \(k + a_i\) 转移来是因为其与某个 \(left\)\(right\) 重合,需特殊处理。

若是并在某段两边,且不为端点:

\[dp_{i , j , k , d} = dp_{i - 1 , j , k , d} \times (2j - d) \]

若是并在某段两边,且为端点:

\[dp_{i , j , k , d} = dp_{i - 1 , j , k + a_i , d - 1} \times (2 - d + 1) \]

然后我们发现这个 \(DP\) 第三维是要处理到 \(\sum a_i\) 的,因为既有加又有减。

所以时间复杂度是 \(O(n^2 \sum a_i)\) 的,寄了。

然后考虑一下优化哈。有这么个东西叫提前处理答案。

对于一个差分 \(a_{i + 1} - a_i\) 他的贡献。

我们发现对于 \(a_i - a_j (i > j)\) 来说,我们知道这个:

\[a_i - a_j = \sum_{k = j + 1}^{i}a_k - a_{k - 1} \]

那么只有左右 \(i < k \le j\)\(a_k - a_{k - 1}\) 才被计算。

那么就是说在当 \(a_{i + 1}\) 加入时:

现在共有 \(j\) 个段吧,那么这 \(j\) 个段里每个数都是小于 \(a_{i + 1}\) 的。

那么加入 \(a_{i + 1}\) 以后,很多数并在了 \(j\) 个段的左右两端。

假设段 \(k\) 在左端未处理 \(a_{i + 1}\) 前数为 \(x\) , 第一个在处理完 \(a_{i + 1}\) 后数为 \(y\)

显然 \(y > a_{i + 1} > x\)

那么 \(y - x\) 的值就有 \(a_{i + 1} - a_i\) 的一份贡献。

再往后,新并在 \(y\) 左的值就不满足条件了。同理, \(k\) 右端第一个新并上的值一样,所有端包括 \(a_{i + 1}\) 所处的端也一样。

那么我们就发现共有 \(2j\) 个位置是符合条件的,是能被贡献上的。当然还要考虑左右极端点,设已有个数为 \(d\) , 所以本差分贡献为 \((2j - d) \times (a_{i + 1} - a_i)\) ( \(j\) 是处理前的段的数量 ) 。

然后就可以得到式子了。 \(DP\) 设计不变,只要将所有的 \(k\) 加减什么数全部改成 \(k_2 =(2j - d) \times (a_{i + 1} - a_i)\) 就可以了。

如果目前的 \(k_2\) 超过 \(L\) 直接不算弃了就行,时间复杂度 \(O(n^2L)\)

#include <bits/stdc++.h>
using namespace std ; 
typedef long long ll ; 
const int N = 101 ; 
const int M = 1010 ; 
const int mod = 1e9 + 7 ; 

int n , m , a[N] ; 
int dp[N][N][M][3] ; 

signed main() {
	ios :: sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ; 
	cin >> n >> m ; 

	if (n == 1) { // 特判 n = 1
		cout << 1 ; return 0 ; 
	}

	for (int i = 1 ; i <= n ; ++ i) cin >> a[i] ; 

	stable_sort(a + 1 , a + n + 1) ; 
	dp[0][0][0][0] = 1 ; 

	for (int i = 0 ; i < n ; ++ i) {
		for (int j = 0 ; j <= i ; ++ j) {
			for (int k = 0 ; k <= m ; ++ k) {
				for (int d = 0 ; d <= 2 ; ++ d) {
					ll k2 = 1ll * (2 * j - d) * (a[i + 1] - a[i]) + 1ll * k ; 
					if (k2 > m || k2 < 0) continue ; 
					if (!dp[i][j][k][d]) continue ; 

					if (j >= 2) dp[i + 1][j - 1][k2][d] = (1ll * dp[i + 1][j - 1][k2][d] + 1ll * dp[i][j][k][d] * (j - 1)) % mod ; // 合并两个区间
					if (j >= 1) dp[i + 1][j][k2][d] = (1ll * dp[i + 1][j][k2][d] + 1ll * dp[i][j][k][d] * (2 * j - d)) % mod ; // 并在一个区间左右且不为端点
					dp[i + 1][j + 1][k2][d] = (1ll * dp[i + 1][j + 1][k2][d] + 1ll * dp[i][j][k][d] * (j + 1 - d)) % mod ; // 重开一个且不为端点
					
					if (d < 2 && j >= 1) dp[i + 1][j][k2][d + 1] = (1ll * dp[i + 1][j][k2][d + 1] + 1ll * dp[i][j][k][d] * (2 - d)) % mod ; //  并在一个区间左右且为端点
					if (d < 2) dp[i + 1][j + 1][k2][d + 1] = (1ll * dp[i + 1][j + 1][k2][d + 1] + 1ll * dp[i][j][k][d] * (2 - d)) % mod ; // 重开一个且为端点
				}
			}
		}
	}

	ll ans = 0 ; 

	for (int i = 0 ; i <= m ; ++ i) {
		ans = (ans + 1ll * dp[n][1][i][2]) % mod ; 
	}

	cout << ans ; 
}

原文链接:https://www.cnblogs.com/hangry/p/18378196

 友情链接:直通硅谷  点职佳