引入
对于一种需要通过相邻两项来维护的一些 DP 问题，通常的 DP 会无法转移。这时便要使用线头 DP。这种 DP 又名连续段 DP，其关键在于维护已近满足条件的不同连续段的贡献总和。
线头 DP 本质上只是一种转移状态，这种状态能与排列成双射的同时，还能只考虑两端的性质来使状态便于记录。它可以最大程度利用两端插入时的良好性质，同时还能与排列集成双射，快速解决这类依赖邻项的问题。
通常，我们设 \(DP_{i, j}\) 表示考虑了前 \(i\) 个元素，形成了 \(j\) 个满足条件的段落。以下将该段落称为线。我们通过这些线通过新建，合并，延续的方法进行转移。
- \(DP_{i, j}\) 可以通过 \(DP_{i - 1, j - 1}\) 转移。这表示新建了一个连续段。
- \(DP_{i, j}\) 可以通过 \(DP_{i - 1, j}\) 转移。这表示延续了一个连续段。
- \(DP_{i, j}\) 可以通过 \(DP_{i - 1, j + 1}\) 转移。这表示合并了一个连续段。
kangaroo
先考虑没有 \(s, t\) 怎么做。一个数必定会同时大于或小于相邻的数。尝试用上面的方法转移。一个线表现为所有数都大于或小于相邻的数。
设 \(DP_{i, j}\) 表示考虑了前 \(i\) 个元素，形成了 \(j\) 个线。我们从小到大加入元素。那么有以下转移。
- \(DP_{i, j} = DP_{i - 1, j - 1} \times j\)。这表示加入了一个新段。原先有 \(j - 1\) 个线，因此可以插在 \(j\) 个空中。注意这里也考虑了延续的情况。
- \(DP_{i, j} = DP_{i - 1, j + 1} \times j\)。这表示合并。因为我们的 \(j\) 元素比前面的大，所以保证可以。
若有 \(s, t\)，我们发现：
- 若 \(i = s \text{或} t\)，有 \(DP_{i, j} = DP_{i - 1, j} + DP_{i - 1, j - 1}\)。这表明合并或新加。
- 若 \(i\) 已过 \(s\) 则不能加头，若 \(i\) 已过 \(t\) 则不能插尾。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e3, Mod = 1e9 + 7;
int n, l, r;
int dp[N][N];
signed main(){
cin >> n >> l >> r;
dp[1][1] = 1;
for(int i = 2; i <= n; i++)
for(int j = 1; j <= n; j++){
if(i == l || i == r)
dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % Mod;
else{
dp[i][j] = dp[i - 1][j - 1] * j % Mod;
if(l < i) dp[i][j] = (dp[i][j] - dp[i - 1][j - 1] + Mod) % Mod;
if(r < i) dp[i][j] = (dp[i][j] - dp[i - 1][j - 1] + Mod) % Mod;
dp[i][j] = (dp[i][j] + dp[i - 1][j + 1] * j % Mod) % Mod;
}
}
cout << dp[n][1] << endl;
return 0;
}
高層ビル街
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 105, Mod = 1e9 + 7;
int n, l, a[N], dp[2][N][1005][2][2];
bool cmp(int x, int y){return x > y;}
void add(int& u, int v){
u %= Mod, v %= Mod;
u = (u + v + Mod) % Mod;
return ;
}
signed main(){
cin >> n >> l;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n, cmp);
// dp[i & 1][cnt][sum][left][right] 表示当前考虑到 a[i]，
// 有 cnt 个连续段，和为 sum，左边和右边是否固定的方案数
// 初始的时候，只加了 1 个数，sum 此时是零
dp[1][1][0][0][0] = 1; dp[1][1][0][0][1] = 1;
dp[1][1][0][1][0] = 1; dp[1][1][0][1][1] = 1;
for(int i = 2; i <= n; i++){
bool u = i & 1, v = !u; // 当前的状态，之前的状态
// 清空当前的状态
for(int cnt = 1; cnt <= i; cnt++) for(int sum = 0; sum <= l; sum++)
dp[u][cnt][sum][0][0] = 0, dp[u][cnt][sum][0][1] = 0,
dp[u][cnt][sum][1][0] = 0, dp[u][cnt][sum][1][1] = 0;
for(int cnt = 1; cnt < i; cnt++) for(int sum = 0; sum <= l; sum++)
for(int L = 0; L <= 1; L++)
for(int R = 0; R <= 1; R++){
// 每一个段落会贡献两个高度，但如果以确定左右就会少贡献
int newSum = sum + (a[i - 1] - a[i]) * (2 * cnt);
if(L) newSum -= (a[i - 1] - a[i]);
if(R) newSum -= (a[i - 1] - a[i]);
if(l < newSum) continue;
// 在之前的块里面加一个新块，块数要大于 1，总共有 cnt - 1 种填法
// 或合并块，也是 cnt - 1 种
if(cnt != 1) add(dp[u][cnt + 1][newSum][L][R], (cnt - 1) * dp[v][cnt][sum][L][R]);
if(cnt != 1) add(dp[u][cnt - 1][newSum][L][R], (cnt - 1) * dp[v][cnt][sum][L][R]);
// 在左右边新建块，要注意 L/R = 0
if(!L) add(dp[u][cnt + 1][newSum][0][R], dp[v][cnt][sum][0][R]),
add(dp[u][cnt + 1][newSum][1][R], dp[v][cnt][sum][0][R]);
if(!R) add(dp[u][cnt + 1][newSum][L][0], dp[v][cnt][sum][L][0]),
add(dp[u][cnt + 1][newSum][L][1], dp[v][cnt][sum][L][0]);
// 在之前的块里面加进一个旧块，块数要大于 1，总共有 2 * cnt - 2 种填法
if(cnt != 1) add(dp[u][cnt][newSum][L][R], 2 * (cnt - 1) * dp[v][cnt][sum][L][R]);
// 在左右边加旧块，要注意 L/R = 0
if(!L) add(dp[u][cnt][newSum][0][R], dp[v][cnt][sum][0][R]),
add(dp[u][cnt][newSum][1][R], dp[v][cnt][sum][0][R]);
if(!R) add(dp[u][cnt][newSum][L][0], dp[v][cnt][sum][L][0]),
add(dp[u][cnt][newSum][L][1], dp[v][cnt][sum][L][0]);
}
}
// 统计答案
int ans = 0;
for(int i = 0; i <= l; i++) add(ans, dp[n & 1][1][i][true][true]);
cout << ans << endl;
return 0;
}