预设型 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_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 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 ;
}