预设型 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\) .
无非分成三种情况：
- \(i\) 自成一个连续段 : 现在有 \(j - 1\) 个连续段，新加的有 \(j\) 种可能性，因此:
\[dp_{i , j , k} += dp_{i - 1 , j - 1 , k - i} \times j
\]
- \(i\) 并在一个连续段里，即变为一个连续段的两端。 \(j\) 个连续段，显然有 \(2j\) 种选法，因此:
\[dp_{i , j , k} += dp_{i - 1 , j , k - i} \times 2j
\]
- \(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_Freadchar 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#endifusing 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 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 ; }
经验首页