首页 > 其他分享 >插入dp学习笔记

插入dp学习笔记

时间：2025-01-19 23:23:24浏览次数：1  
标签：int LL 笔记 插入 trans dp mod

定义

插入 \(\text{dp}\) 适用于计数、求最优解且具有选择、排列元素过程等题目。
插入 \(\text{dp}\) 大致分为两类：

  • 乱搞型：状态定义天马行空，但始终围绕着将新元素插入到旧元素已有集合中
  • 套路型：\(dp_{i, j}\) 表示前 \(i\) 个数，现在构成 \(j\) 个连续段的方案数\(/\)最优解，此外根据实际情况添加状态，转移则是用新元素新建连续段\(/\)合并两个连续段\(/\)扩张连续段左侧或右侧

乱搞型

模板

说是模板，其实这种类型谈不上什么模板，每一题的状态定义几乎都不一样，都有奇奇怪怪的某一维，所以此题也可以视为经典题。
CF466D
定义 \(dp_{i, j}\) 表示考虑完前 \(i\) 个数且前 \(i\) 个数都已推平，尚有 \(j\) 个区间未闭合的方案数。
对于转移，我们有需要满足推平下一个数的条件，以及同一位置不能同时开启\(/\)关闭多于 \(1\) 个区间，根据这个思路去推状态转移式即可。

/*
address:https://codeforces.com/problemset/problem/466/D
AC 2024/12/24 20:45
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
const int N = 2005;
inline void trans(int& x, int y) { x = (x + y) % mod; }
int dp[N][N];
int n, h;
int a[N];
int main() {
    scanf("%d%d", &n, &h);
    for (int i = 1;i <= n;i++) scanf("%d", &a[i]), a[i] = h - a[i];
    dp[0][0] = 1;
    for (int i = 0;i < n;i++)
        for (int j = 0;j <= i;j++) {
            int x = a[i + 1];
            if (j + 1 == x) {
                trans(dp[i + 1][j + 1], dp[i][j]);              //开启一个新区见
                trans(dp[i + 1][j], LL(dp[i][j]) * j % mod);    //关闭又开启一个新区间
                trans(dp[i + 1][j], dp[i][j]);                  //开启一个区间后马上关闭该区间
            }
            if (j == x) {
                if (j > 0) trans(dp[i + 1][j - 1], LL(dp[i][j]) * j % mod); //关闭一个区间
                trans(dp[i + 1][j], dp[i][j]);                  //什么事都不干
            }
        }
    printf("%d", dp[n][0]);                                     //最后所有区间都关闭了
    return 0;
}

实例

AT_dp_t
考虑插入一个数时要考虑插入的数与最后一个数的相对大小关系，并不在意绝对数值，同时方案数计算依赖于又多少数满足条件，所以定义 \(dp_{i, j}\) 表示考虑完前 \(i\) 个数，剩下的数有 \(j\) 个数比位置 \(i\) 填的数小的方案数。这时考虑转移，对于当前字符，选择更大\(/\)更小的，让后转移过去，发现转移要 \(O(N)\) ，但使用差分或前缀和优化可以砍掉，最后是 \(O(N^2)\) 。

/*
address:https://atcoder.jp/contests/dp/tasks/dp_t
AC 2024/12/24 21:11
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3005;
const int mod = 1e9 + 7;
char s[N];
int n;
LL dp[N][N], tmp[N];
inline void trans(LL& x, LL y) { x = (x + y + mod) % mod; }
int main() {
    scanf("%d%s", &n, s + 1);
    for (int i = 0;i < n;i++) dp[1][i] = 1;
    for (int i = 1;i <= n;i++) {
        fill(tmp, tmp + n + 1, 0);
        for (int j = 0;j <= n;j++)
            if (s[i] == '>') trans(tmp[0], dp[i][j]), trans(tmp[j], -dp[i][j]);
            else trans(tmp[j], dp[i][j]), trans(tmp[n - i], -dp[i][j]);
        for (int j = 1;j <= n;j++) trans(tmp[j], tmp[j - 1]);
        for (int j = 0;j <= n;j++) dp[i + 1][j] = tmp[j];
    }
    LL ans = 0;
    for (int i = 0;i < n;i++) trans(ans, dp[n][i]);
    printf("%lld", ans);
    return 0;
}

拓展练习

CF626F 可以排序，定义 \(dp_{i, j, k}\) 表示前 \(i\) 个，有 \(j\) 个小组仍未确定，总不平衡度为 \(k\) 的方案数，卡卡能过，也有通过优化砍掉一维时间的做法，都可以。
Code

套路型

先来思考一个问题，怎么用插入dp求 \(n!\) ，其实就是排列 \(n\) 个元素的方案数，怎么求呢？定义 \(dp_{i, j}\) 表示前 \(i\) 个元素构成 \(j\) 个连续段的方案数，根据定义，我们有如下转移：

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

最终答案即为 \(dp_{n, 1}\) 。
听起来很奇怪，但这是这一类插入 \(\text{dp}\) 的通用套路，屡试不爽。

实例

Seatfriends
先不管相隔的距离，以套路插入 \(\text{dp}\) 计算若不考虑连续段间需至少隔一个空位时的答案，然后枚举连续段数量并用组合数统计插入空位的方案数,同时特判 \(m = 1\) ，不然会出事，具体可参考我的博客 。
Phoenix and Computers
按套路，定义 \(dp_{i, j}\) 表示已开了 \(i\) 台电脑，构成了 \(j\) 个连续段。
考虑转移，对于新建一个连续段，我们可以在 \(j + 1\) 个空里插，所以转移式是

\[dp_{i, j} \times (j + 1) \to dp_{i + 1, j + 1} \]

对于扩展连续段，我们可以直接在左右两侧添加，也可以隔一个位置加，同时把隔的那个位置自动打开，故有以下转移

\[dp_{i, j} \times 2j \to dp_{i + 1, j}, dp_{i + 2, j} \]

对于合并连续段,由于两个连续段间若距离为 \(1\) 的话中间那台电脑就会自动开启，就已经是一个连续段了，与定义不符，故两个连续段间空位数量为 \(2\) 或 \(3\) ，所以有以下转移

\[dp_{i, j} \times 2(j - 1) \to dp_{i + 2, j - 1} \]

固定区间间距离为 \(3\) ，开中间那台。

\[dp_{i, j} \times (j - 1) \to dp_{i + 3, j - 1} \]

这时就有朋友要问了：“作者作者，你为什么在扩展区间和新建区间不考虑区间间的距离？现在又凭什么能固定距离为 \(2\) 和 \(3\) 呢？”
观察一下我们的定义，是没有考虑绝对距离的，只有考虑相对间距，对于两个区间间的距离，我们也就可以随意调整，同时转移式的正确与齐全也带来了一种“自适应性”，能保证不合法的状态一定不会转移到最终状态，例如当 \(n = 3\) ，\(2, 2\) 是没法转移到 \(3, 1\) 的状态的，所以不用考虑提到的问题。
参考代码：

/*
address:https://codeforces.com/problemset/problem/1515/E
AC 2024/12/28 10:41
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 405;
int mod;
int n;
LL dp[N][N];
inline void trans(LL& x, LL y) { x = (x + y) % mod; }
int main() {
    scanf("%d%d", &n, &mod);
    dp[0][0] = 1;
    for (int i = 0;i < n;i++)
        for (int j = 0;j <= i;j++) {
            trans(dp[i + 1][j + 1], dp[i][j] * (j + 1));
            trans(dp[i + 1][j], dp[i][j] * j << 1);
            trans(dp[i + 2][j], dp[i][j] * j << 1);
            if (j > 1) {
                trans(dp[i + 2][j - 1], dp[i][j] * (j - 1 << 1));
                trans(dp[i + 3][j - 1], dp[i][j] * (j - 1));
            }
        }
    printf("%lld", dp[n][1]);
    return 0;
}

Ant Man
先观察一下题目，发现对于题目中的计算公式可以费用提前计算但前提是在当前插入数的对应方向会继续插入数，可题目已经定义了起点和终点，所以除了起点和终点外，其他座椅的左右两侧都一定会继续插入椅子，故放心大胆使用费用提前计算。
定义 \(dp_{i, j}\) 表示将前 \(i\) 把椅子的访问顺序排完，有 \(j\) 个连续段的最小距离。
考虑转移：
段新增：若插入的数不为 \(s\) 或 \(e\) ，则会添加 \(-2x_i + b_i + d_i\) 否则只考虑右\(/\)左侧添加元素贡献，统共是：

\[dp_{i + 1, j + 1} \leftarrow dp_{i, j} - x_{i + 1} + d_{i + 1} (i + 1 = s) \]

\[dp_{i + 1, j + 1} \leftarrow dp_{i, j} - x_{i + 1} + b_{i + 1} (i + 1 = e) \]

\[dp_{i + 1, j + 1} \leftarrow dp_{i, j} - 2x_{i + 1} + d_{i + 1} + b_{i + 1} (i + 1 \ne s \wedge i + 1 \ne e) \]

同时在添加非 \(s\) 和 \(e\) 的数时，当 \(s\) 和 \(e\) 已插入完毕且当前只有 \(1\) 个连续段，再插入连续段是不合法的，所以还要特判 \(i + 1 <= s \vee i + 1 <= e \vee j + 1 > 2\) 才能进行第 \(3\) 个转移。
段扩张，以同样思路进行分析，考虑规避不合法情况，得到以下转移式：

\[dp_{i + 1, j} \leftarrow dp_{i, j} + x_{i + 1} + c_{i + 1} (i + 1 = s) \]

\[dp_{i + 1, j} \leftarrow dp_{i, j} + x_{i + 1} + a_{i + 1} (i + 1 = e) \]

\[dp_{i + 1, j} \leftarrow dp_{i, j} + b_{i + 1} + c_{i + 1} (i + 1 \ne s \wedge i + 1 \ne e) \]

\[dp_{i + 1, j} \leftarrow dp_{i, j} + a_{i + 1} + d_{i + 1} (i + 1 \ne s \wedge i + 1 \ne e) \]

段合并：

\[dp_{i + 1, j - 1} \leftarrow dp_{i, j} + 2x_{i + 1} + a{i + 1} + c_{i + 1} (i + 1 \ne s \wedge i + 1 \ne e) \]

代码：

/*
address:https://codeforces.com/problemset/problem/704/B
AC 2025/1/3 20:59
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5005;
int n, s, e;
int x[N], a[N], b[N], c[N], d[N];
LL dp[N][N];
inline void trans(LL& x, LL y) { x = x < y ? x : y; }
int main() {
    scanf("%d%d%d", &n, &s, &e);
    for (int i = 1;i <= n;i++) scanf("%d", &x[i]);
    for (int i = 1;i <= n;i++) scanf("%d", &a[i]);
    for (int i = 1;i <= n;i++) scanf("%d", &b[i]);
    for (int i = 1;i <= n;i++) scanf("%d", &c[i]);
    for (int i = 1;i <= n;i++) scanf("%d", &d[i]);
    for (int i = 0;i <= n;i++)
        for (int j = 0;j <= n;j++) dp[i][j] = 1e18;
    dp[0][0] = 0;
    for (int i = 0;i < n;i++)
        for (int j = 0;j <= i;j++)
            if (i + 1 == s) {
                trans(dp[i + 1][j + 1], dp[i][j] - x[i + 1] + d[i + 1]);
                if (j > 0) trans(dp[i + 1][j], dp[i][j] + x[i + 1] + c[i + 1]);
            }
            else if (i + 1 == e) {
                trans(dp[i + 1][j + 1], dp[i][j] - x[i + 1] + b[i + 1]);
                if (j > 0) trans(dp[i + 1][j], dp[i][j] + x[i + 1] + a[i + 1]);
            }
            else {
                if (i + 1 <= s || i + 1 <= e || j + 1 > 2) trans(dp[i + 1][j + 1], dp[i][j] - (x[i + 1] << 1) + d[i + 1] + b[i + 1]);
                if (j > 0) {
                    if (j > 1 || i + 1 < s) trans(dp[i + 1][j], dp[i][j] + b[i + 1] + c[i + 1]);
                    if (j > 1 || i + 1 < e) trans(dp[i + 1][j], dp[i][j] + a[i + 1] + d[i + 1]);
                }
                if (j > 1) trans(dp[i + 1][j - 1], dp[i][j] + (x[i + 1] << 1) + a[i + 1] + c[i + 1]);
            }
    printf("%lld", dp[n][1]);
    return 0;
}

Boss

最后给大家隆重介绍插入 \(dp\) 的Boss：UTS Open '21 P7 - April Fools
大致说一下，先排序，定义 \(dp_{i, j, k, 0/1/2}\) 表示前 \(i\) 个数，有 \(j\) 个连续段以 \(\text{MSB}(A_i) - 1\) 结尾，有 \(k\) 个连续段以 \(\text{MSB}(A_i)\) 结尾，结尾区间的结尾为 \(\text{MSB}(A_i)\) / $\text{MSB}(A_i) - 1 $ / \(\le \text{MSB}(A_i) - 2\) 的方案数。分类讨论手推式子转移，省流：\(34\) 个转移，具体看我的博客 。

/*
address:http://vjudge.net/problem/DMOJ-utso21p7
AC 2025/1/10 22:06
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 505;
const int mod = 1e9 + 7;
int n;
int a[N], f[N];
int dp[2][N][N][3];
inline void trans(int& x, const int y, const int z) { x = (x + 1ll * y * z % mod) % mod; }
int main() {
    scanf("%d", &n);
    for (int i = 1;i <= n;i++) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    for (int i = 1;i <= n;i++)
        for (int j = 31;j >= 0;j--)
            if (a[i] >> j & 1) {
                f[i] = j;
                break;
            }
    dp[1][0][1][0] = 1;
    for (int i = 1;i < n;i++) {
        for (int j = 0;j <= i + 1;j++)
            for (int k = 0;k + j <= i + 1;k++)
                for (int l = 0;l < 3;l++) dp[i + 1 & 1][j][k][l] = 0;
        for (int j = 0;j <= i;j++)
            for (int k = 0;k + j <= i;k++) {
                const int c0 = dp[i & 1][j][k][0], c1 = dp[i & 1][j][k][1], c2 = dp[i & 1][j][k][2];
                const int  l = (i & 1) ^ 1;
                if (f[i + 1] - f[i] == 0) {
                    // new
                    trans(dp[l][j][k + 1][0], c0, j + k + 1);
                    trans(dp[l][j][k + 1][1], c1, j + k);
                    trans(dp[l][j][k + 1][0], c1, 1);
                    trans(dp[l][j][k + 1][2], c2, j + k + 1);
                    // extend
                    trans(dp[l][j][k][0], c0, j + k);
                    trans(dp[l][j][k][1], c1, j + k);
                    trans(dp[l][j][k][2], c2, j + k + 1);
                    if (j > 0) {
                        trans(dp[l][j - 1][k + 1][0], c0, j);
                        trans(dp[l][j - 1][k + 1][1], c1, j - 1);
                        trans(dp[l][j - 1][k + 1][0], c1, 1);
                        trans(dp[l][j - 1][k + 1][2], c2, j);
                    }
                    // merge
                    if (j > 0) {
                        trans(dp[l][j - 1][k][0], c0, j);
                        trans(dp[l][j - 1][k][1], c1, j - 1);
                        trans(dp[l][j - 1][k][2], c2, j);
                    }
                }
                if (f[i + 1] - f[i] == 1) {
                    // new
                    if (j == 0) trans(dp[l][k][1][0], c0, 1);
                    if (j == 0) trans(dp[l][k][1][1], c0, k);
                    if (j == 1) trans(dp[l][k][1][2], c1, k + 1);
                    if (j == 0) trans(dp[l][k][1][2], c2, k + 1);
                    // extend
                    if (j == 0) trans(dp[l][k][0][1], c0, k);
                    if (j == 0 && k > 0) trans(dp[l][k - 1][1][1], c0, k - 1);
                    if (j == 0 && k > 0) trans(dp[l][k - 1][1][0], c0, 1);
                    if (j == 1) trans(dp[l][k][0][2], c1, k + 1);
                    if (j == 1 && k > 0) trans(dp[l][k - 1][1][2], c1, k);
                    if (j == 0) trans(dp[l][k][0][2], c2, k + 1);
                    if (j == 0 && k > 0) trans(dp[l][k - 1][1][2], c2, k);
                    // merge
                    if (k > 0) {
                        if (j == 0) trans(dp[l][k - 1][0][1], c0, k - 1);
                        if (j == 1) trans(dp[l][k - 1][0][2], c1, k);
                        if (j == 0) trans(dp[l][k - 1][0][2], c2, k);
                    }
                }
            }
        const int j = i & 1, k = j ^ 1;
        if (f[i + 1] - f[i] >= 2) {
            // new
            trans(dp[k][0][1][2], dp[j][1][0][1], 1);
            trans(dp[k][0][1][2], dp[j][0][1][0], 1);
            trans(dp[k][0][1][2], dp[j][0][0][2], 1);
            // extend
            trans(dp[k][0][0][2], dp[j][1][0][1], 1);
            trans(dp[k][0][0][2], dp[j][0][1][0], 1);
            trans(dp[k][0][0][2], dp[j][0][0][2], 1);
        }
    }
    printf("%d\n", ((dp[n & 1][1][0][1] + dp[n & 1][0][1][0]) % mod + dp[n & 1][0][0][2]) % mod);
    return 0;
}

总结

插入 \(dp\) 在学之前去做的话做出的概率无限接近于 \(0\) ，因为无论是乱搞型还是套路型的定义都非常地巧妙，同时这一个 \(\text{dp}\) 地可变性很多，也比较耗脑子，需要多刷题归纳总结各种套路。所以说 \(\text{dp}\) 是人类智慧的结晶是有道理的。

宝剑锋从磨砺出，梅花香自苦寒来

标签：int,LL,笔记,插入,trans,dp,mod
From： https://www.cnblogs.com/keysky/p/18680483

相关文章

  • 代码随想录：二叉搜索时的插入
    /***Definitionforabinarytreenode.*structTreeNode{*intval;*TreeNode*left;*TreeNode*right;*TreeNode():val(0),left(nullptr),right(nullptr){}*TreeNode(intx):val(x),left(nullptr),right(nullptr){}*......
  • 2024秋季学期 电子技术基础期末复习笔记
    电路分析模拟电路......
  • 遗传算法个人入门笔记
    先举一个简单的求解例子：变量x,y函数f(x,y)=(x-5)^2+(y+3)^2-5求最小值。deftest(x,y):return(x-5)**2+(y-3)**2-5显然，这个函数在x=5，y=3时取最小值-5。现在我们尝试用遗传算法解决之。遗传算法主要是模拟生物进化的过程，将每一个值视作一个生物，有自己的......
  • 蓝桥杯备赛笔记（九）动态规划（一）
    1.动态规划基础(1)线性DP1）什么是DP（动态规划）DP（动态规划）全称DynamicProgramming，是运筹学的一个分支，是一种将复杂问题分解成很多重叠的子问题，并通过子问题的解得到整个问题的解的算法。在动态规划中有一些概念：状态：就是形如dp[i][j]=val的取值，其中i，j为下标，也是用于描述、......
  • 如何解决WordPress打开网页时出现“建立数据库连接时出错”的问题？
    常见原因数据库配置文件错误：wp-config.php文件中的数据库配置信息不正确。MySQL数据库服务问题：MySQL数据库服务未启动或数据库账号密码错误。网络连接问题：如果使用外部数据库，可能需要检查网络连接和端口配置。解决方法方法一：检查数据库配置文件打开wp-config.php文件：......
  • 解决WordPress上传至虚拟主机后网站无法正常显示的问题
    用户将WordPress程序上传至虚拟主机空间中，配置了wp-config.php文件并上传，但网站无法正常显示，提示错误信息。回答： 您好，感谢您的反馈。根据您的描述，可能是由于数据库配置不正确导致的。具体来说，数据库配置连接虚拟主机数据库没有数据，访问会跳转到安装目录，原因是未导入数据库备份文......
  • 25/1/14 算法笔记＜强化学习＞ CBR加强化学习
    CBR,基于案例的推理，它是一种基于过去的实际经验或经历的推理，他可以根据过往的案例找到与当前案例最相关的案例，然后对该案例做改动来解决当前的问题。CBR的过程CBR可以看作一个循环过程：相似按键检索-->案例重用-->案例修改-->案例学习遇到新问题时，将新问题通过案例描述输入CB......
  • Java初学者笔记-06、Stream流
    什么是Stream流JDK8开始新增的一套API，可以用于链式操作集合或者数组的数据。优势：Stream流大量的结合了Lambda的语法风格来编程，功能强大，性能高效，代码简洁，可读性好。list.stream().filter(s->s.startswith("张")).filter(s->s.Length()==3).collect(Collectors.toList());......
  • Maui学习笔记-CommunityToolkit.Maui动画案例
    动画元素在CommunityToolkit.Maui工具包中提供了AnimationBehavior和BaseAnimation类。AnimationBehavior作用在视图UI元素，并用作动画的容器。BaseAnimation是实现动画逻辑的基类。下面这个案例是使一个按钮实现淡入淡出的效果在主页的隐藏文件中创建一个类继承Ba......
  • 计算机图形学技术笔记~直线Bresenham算法
    研究内容：（1）基于图形设备的基本图形元素的生成算法，如用光栅图形显示器生成直线、圆弧、二次曲线、封闭边界内的图案填充等。布雷森汉姆直线Bresenham算法：(1)利用距离误差大小比较判断符号；(2)推导递推公式；(3)不必计算直线斜率，不用浮点数；(4)只用整数加减法和乘2运算，乘2运......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99