某种DP
感觉没见到固定的专业术语，我习惯叫它为预设性 \(DP\) ，也有人叫它连续段 \(DP\) ，插入 \(DP\)
为什么这么说？
因为 \(DP\) 的过程就是预先留出位置，然后把元素按照 某种顺序一个一个插入， \(DP\) 的状态记录 插入的元素个数 和 已有的连续段
（或许也算一种计数 \(DP\) ?）
这样说不好理解，直接看例题，做几道例题就明白了
这种 \(DP\) 一般有（连续段）有序和无序两种，一般的题目两种都适用，只不过根据定义转移会有区别
最最最模板题
这里考虑连续段有序
设 \(dp_{i, j}\) 表示当前已经有 \(i\) 个电脑被开机，一共有 \(j\) 个连续段的方案数
转移：
打开一个电脑构成一个新的连续段，已经有 \(j\) 个连续段，新连续段可以放在 \(j + 1\) 个缝隙里：
\(dp_{i + 1, j + 1} += dp_{i, j} \times (j + 1)\)
打开一个电脑紧贴着一个连续段，可以有 \(j\) 个连续段两边一共 \(2j\) 个位置放
$ dp_{i + 1, j} += dp_{i, j} \times 2 \times j $
打开一个电脑和一个连续段隔一个位置，一次性打开两个电脑，可以有 \(j\) 个连续段两边一共 \(2j\) 个位置放
$ dp_{i + 2, j} += dp_{i, j} \times 2 \times j $
打开一个电脑放在两个连续段中间，考虑连续段中间隔了两个还是三个（隔了一个的不合法，肯定开机了）
$ dp_{i + 2, j - 1} += dp_{i, j} \times (j - 1) \times 2 $
$ dp_{i + 3, j - 1} += dp_{i, j} \times (j - 1) $
最终答案为 \(dp_{n, 1}\)
我的代码
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define re register
#define ll long long
#define ull unsigned long long
using namespace std;
inline int read()
{
int x = 0, f = 0; char c = getchar();
while (c < '0') f |= (c == '-'), c = getchar();
while (c >= '0') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f ? -x : x;
}
const int N = 2010;
ll n, mod, f[N][N];
int main ()
{
n = read(), mod = read();
f[1][1] = 1;
for (re ll i = 1; i <= n; ++i)
{
for (re ll j = 1; j <= n; ++j)
{
(f[i + 1][j + 1] += (j + 1) * f[i][j] % mod) %= mod;
(f[i + 2][j] += 2 * j * f[i][j] % mod) %= mod;
(f[i + 1][j] += 2 * j * f[i][j] % mod) %= mod;
(f[i + 2][j - 1] += 2 * (j - 1) * f[i][j] % mod) %= mod;
(f[i + 3][j - 1] += (j - 1) * f[i][j] % mod) %= mod;
}
}
printf ("%lld\n", f[n][1]);
return 0;
}
这里考虑连续段无序
（题解区有连续段有序的DP转移）
这里直接把 \(r_i - 1\)，便于统计，以下都按照 \(r_i - 1\) 说明
注意到两个磁铁中间的位置至少是两个磁铁的半径的最大值
我们可以先让所有的磁铁中间的位置都是刚好满足，最后算出总直径，总长度 - 总直径的位置随便插入到磁铁中（这里的直径认为是最左边的磁铁到最右边的磁铁这一段，不包含两边磁铁向外延伸的半径）
因为我们只考虑当前插入的磁铁，为了避免前面的磁铁对我们的影响，我们将磁铁按照半径从小到大插入
我们还要维护总直径，于是设 \(dp_{i, j, k}\) 表示当前插入前 \(i\) 个磁铁，形成了 \(j\) 个连续段（紧密排列，中间没有多余缝隙），总直径为 \(k\) 的方案数
转移：
新开一个连续段，此时直径不变： \(dp_{i + 1, j + 1, k} += dp_{i, j, k}\)
紧贴着某个连续段： \(dp_{i + 1, j, k + r_i} += dp_{i, j, k} \times j \times 2\)
合并两个连续段： \(dp_{i + 1, j - 1, k + 2 \times r_i} += dp_{i, j, k} \times 2 \times C_{j}^{2}\)
我的代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
int read()
{
int x = 0; bool f = false; char c = getchar();
while(c != EOF && c < '0') f |= (c == '-'), c = getchar();
while(c != EOF && c >= '0') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f ? -x : x;
}
const ll mod = 1e9 + 7;
const int N = 55, M = 1e4 + 5;
ll n, l;
ll r[N], f[N][N][M]; // 前i个磁铁，组成了j个团，所有团的直径为k的方案数
ll jc[M], inv[M];
ll C(int n, int m)
{
if(n < 0 || m < 0 || n < m) return 0;
return jc[n] * inv[m] % mod * inv[n - m] % mod;
}
void into()
{
jc[0] = inv[0] = jc[1] = inv[1] = 1;
for(int i = 2; i <= 10000; ++i) jc[i] = jc[i - 1] * i % mod, inv[i] = (mod - mod / i) * inv[mod % i] % mod;
for(int i = 2; i <= 10000; ++i) inv[i] = inv[i] * inv[i - 1] % mod;
}
int main()
{
n = read(), l = read();
into();
for(int i = 1; i <= n; ++i) r[i] = read() - 1;
sort(r + 1, r + n + 1);
f[1][1][0] = 1;
for(int i = 2; i <= n; ++i)
for(int j = 1; j <= n; ++j)
for(int k = 0; k <= l; ++k)
{
f[i][j][k] += f[i - 1][j - 1][k];
if(k >= r[i]) f[i][j][k] += 2ll * j * f[i - 1][j][k - r[i]];
if(k >= 2 * r[i]) f[i][j][k] += 1ll * j * (j + 1) * f[i - 1][j + 1][k - 2 * r[i]];
f[i][j][k] %= mod;
}
ll ans = 0;
for(int i = 0; i <= l; ++i) ans += C(l - i, n) * f[n][1][i] % mod;
printf("%lld\n", ans % mod);
return 0;
}
这里考虑连续段有序
首先为了避免前面插入的数对当前插入的数的影响，我们从 \(1\) 到 \(n\) 顺序插入，这样当前插入的数就是最大值
设 \(dp_{i, j}\) 表示插入了 \(i\) 个数，组成 \(j\) 个连续段的方案数
新开一个连续段，这里要注意如果已经填了左端点或者右端点，那么就不可以在左端点左边或者右端点右边填了：
$ dp_{i + 1, j + 1} += dp_{i, j} \times ((j + 1) - [i > S] - [i > T]) $
不考虑紧贴着放，紧贴着放最终会导致方案不合法
考虑合并两个连续段，这样就满足题目 “小大小” 或者 “大小大” 的放置要求了：
$ dp_{i + 1, j - 1} += dp_{i, j} \times (j - 1) $
当枚举到 \(S\) 或 \(T\) 时，它们不能合并两个连续段，只能单独成连续段或者和一个连续段合并
$ dp_{i + 1, j + 1} += dp_{i, j} $
$ dp_{i + 1, j} += dp_{i, j} $
我的代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
int read()
{
int x = 0; bool f = false; char c = getchar();
while(c != EOF && c < '0') f |= (c == '-'), c = getchar();
while(c != EOF && c >= '0') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f ? -x : x;
}
const int N = 2e3 + 5;
const int mod = 1e9 + 7;
int n, S, T;
ll dp[N][N];
int main()
{
n = read(), S = read(), T = read();
dp[0][0] = 1;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= n; ++j)
{
if(i == S || i == T) dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % mod;
else dp[i][j] = (dp[i - 1][j - 1] * (j - (i > S) - (i > T)) + dp[i - 1][j + 1] * j) % mod;
}
}
printf("%lld\n", dp[n][1]);
return 0;
}
逐渐暴躁，后面的题解大概不会很认真的写了
这里考虑 连续段有序
我最开始的思路是将每个数从小到大插入，插入的时候如果紧贴着，那么它是绝对值较大的数，如果有空位等待后面的数来插入，那么它是绝对值较小的数，有点费用提前计算的感觉
然而这种方法的状态和值域有关，且有负数状态，时间上可能过不去，故没有实现代码
考虑将所有的数从小到大排序，那么 \(a_r - a_l\) 可以表示成
$ \sum_{i = l}^{r - 1} a_{i + 1} - a_i $
也就是第 \(l\) 个数插入后，它旁边的一个位置一直到第 \(r\) 个数插入后才消失，这个位置产生的贡献是 $ \sum_{i = l}^{r - 1} a_{i + 1} - a_i $
设 $ f_{i, j, k, l} $ 表示插入了 \(i\) 个数，有 \(j\) 个连续段，当前的权值为 \(k\) ，两端一共被插入了 \(l\) 个数$ (0 \le l \le 2) $
首先计算新状态的权值，为 $k' = k + (a_{i + 1} - a_i) \times (2 \times j - l) $
转移
考虑一个数是否放两边，放两边的话是单独成段还是合并一个连续段
不放两边的话是单独成段还是合并一个或两个连续段
$ f_{i + 1, j + 1, k', l + 1} += f_{i, j, k, l} \times (2 - l) $
$ f_{i + 1, j, k', l + 1} += f_{i, j, k, l} \times (2 - l) $
$ f_{i + 1, j + 1, k', l} += f_{i, j, k, l} \times (j + 1 - l) $
$ f_{i + 1, j, k', l} += f_{i, j, k, l} \times (2 \times j - l) $
$ f_{i + 1, j - 1, k', l} += f_{i, j, k, l} \times (j - 1) $
我的代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
int read()
{
int x = 0; bool f = false; char c = getchar();
while(c != EOF && c < '0') f |= (c == '-'), c = getchar();
while(c != EOF && c >= '0') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f ? -x : x;
}
const ll mod = 1e9 + 7;
const int N = 105, M = 1005;
int n, L;
ll a[N], f[N][N][M][3];
void add(ll &a, ll b){ a = a + b >= mod ? a + b - mod : a + b; }
int main()
{
n = read(), L = read();
for(int i = 1; i <= n; ++i) a[i] = read();
if(n == 1) return !printf("1\n");
sort(a + 1, a + n + 1);
f[1][1][0][0] = 1, f[1][1][0][1] = 2;
for(int i = 1; i < n; ++i)
for(int j = 1; j <= i; ++j)
for(int k = 0; k <= L; ++k)
for(int l = 0; l <= 2; ++l)
{
ll kk = k + (a[i + 1] - a[i]) * (2 * j - l);
if(kk > L || !f[i][j][k][l]) continue;
if(l < 2) add(f[i + 1][j][kk][l + 1], f[i][j][k][l] * (2 - l) % mod);
if(l < 2) add(f[i + 1][j + 1][kk][l + 1], f[i][j][k][l] * (2 - l) % mod);
add(f[i + 1][j + 1][kk][l], f[i][j][k][l] * (j + 1 - l) % mod);
add(f[i + 1][j][kk][l], f[i][j][k][l] * (2 * j - l) % mod);
add(f[i + 1][j - 1][kk][l], f[i][j][k][l] * (j - 1) % mod);
}
ll ans = 0;
for(int i = 0; i <= L; ++i) ans += f[n][1][i][2];
printf("%lld\n", ans % mod);
return 0;
}
这道题就可以用上一道题我说的那种方法（费用提前计算的感觉），按照 \(p_i\) 从小到大插入，考虑是作为较小数贡献还是较大数贡献
转移时注意是否合法，在第 \(n\) 个元素插入之前且两端的数都插入后，连续段不能为 \(1\)
我的代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
int read()
{
int x = 0; bool f = false; char c = getchar();
while(c != EOF && c < '0') f |= (c == '-'), c = getchar();
while(c != EOF && c >= '0') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f ? -x : x;
}
const int N = 5005;
int n, S, T;
ll x[N], a[N], b[N], c[N], d[N], f[N][N];
int main()
{
n = read(), S = read(), T = read();
for(int i = 1; i <= n; ++i) x[i] = read();
for(int i = 1; i <= n; ++i) a[i] = read();
for(int i = 1; i <= n; ++i) b[i] = read();
for(int i = 1; i <= n; ++i) c[i] = read();
for(int i = 1; i <= n; ++i) d[i] = read();
memset(f, 0x3f, sizeof(f));
f[0][0] = 0;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= i; ++j)
{
if(i == S)
{
f[i][j] = min(f[i][j], f[i - 1][j - 1] + d[i] - x[i]);
if(i > T && i != n && j == 1) continue;
f[i][j] = min(f[i][j], f[i - 1][j] + x[i] + c[i]);
}else if(i == T)
{
f[i][j] = min(f[i][j], f[i - 1][j - 1] + b[i] - x[i]);
if(i > S && i != n && j == 1) continue;
f[i][j] = min(f[i][j], f[i - 1][j] + x[i] + a[i]);
}else
{
int l = j - (i > S), r = j - (i > T);
if(l) f[i][j] = min(f[i][j], f[i - 1][j] + b[i] + c[i]);
if(r) f[i][j] = min(f[i][j], f[i - 1][j] + d[i] + a[i]);
f[i][j] = min(f[i][j], f[i - 1][j - 1] + d[i] + b[i] - 2 * x[i]);
if(i > S && i > T && i < n && j == 1) continue;
f[i][j] = min(f[i][j], f[i - 1][j + 1] + c[i] + a[i] + 2 * x[i]);
}
}
printf("%lld\n", f[n][1]);
return 0;
}
记得校内模拟赛出过三道这样的 \(DP\) 题，有时间再补上
标签：int,long,times,插入,DP,&&,dp,某种 From： https://www.cnblogs.com/wenqizhi/p/17109756.html