zhengjun dp

题目链接 139. 单词拆分 思路 分析动态规划题目的时候只需要考虑最后一个阶段，因为所有的阶段转化都是相同的，考虑最后一个阶段容易发现规律 在数组的动态规划问题中，一般 dp[i] 都是表示以 nums[i] 为结尾的状态；dp[i][j] 分别表示 以 nums1[i] 和 nums2[j] 为 ......

一道数位dp的题 无链接，朋友问的。 题目 定义“好数”为倍数为7且数字中不含4的数，编写程序在1秒内找出第n（1<n<1e12）个好数 代码 #include<bits/stdc++.h> #define ll long long using namespace std; const int N ......

你也许会好奇为什么没有 04.16 的训练记录，昨天农了一天 O(∩_∩)O。 Vacation https://atcoder.jp/contests/dp/tasks/dp_c 小明在接下来的 $n$ 天，可以选择三种事件并获得 $a_i / b_i / c_i$ 的快乐值，但是他不能连续两天及 ......

https://codeforces.com/contest/1320/problem/A ###A. Journey Planning 题目大意： 给定一组数，问我们ai-aj==i-j的时候就可以把ai的值加起来，问我们可以凑到的最大总值是多少？ input 6 10 7 1 9 10 15 o ......

例题： 洛谷P2900 [USACO08MAR]Land Acquisition G 分析与转化 可以发现，有一些东西是完全没用的 当一个矩形的长和宽都比另一个矩形小的时候，这个矩形就是废的，因为他完全可以套在另外那个矩形一起买 这时候我们就能发现：我们得到了一个长度递减，宽度递增的矩形序列 而要求 ......

思路 1 换根DP: 第一次dfs 预处理出每一个儿子树的 最长距离1 和次长距离2 第二次开始换根DP, 本点到其他 点的距离最长 : 分别考虑 一个是父亲上下来的点len3, 一个是兄弟节点, 就是父亲的最长距离len1或者 次长距离len2, 当然这道题要 k个人所在的节点才会产生权值 思路2 ......

本题大意：给出n，m，s，t，k，n个点，m条路，求s到t的最短路，并且最多k条路免费，然后给出m行，u，v，w，代表u到v有一条权值为w的双向路。 思路: 就是dj最短路 + 一个dp维度的处理, dp[i][j], 到第i个节点用了多少个免费的路径的最短路径 ......

一、题意：找到第k（k上限1e12）大的，不包括4并且能被7整除的数。 题解：二分+数位dp。 #include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; ......

题目链接：https://codeforces.com/contest/1816/problem/F 题解： 一道有趣的题。 首先发现 $m=1$ 和 $m\geq 3$ 时结论是平凡的。$m=1$ 时结论显然，下面讨论一下 $m\geq 3$ 时： 首先可以构造 $[x, (n-x)/2, (n- ......

题目描述 有一长度为 N(1<=Ｎ<=10) 的地板，给定两种不同瓷砖：一种长度为 1，另一种长度为 2，数目不限。要将这个长度为 N 的地板铺满，一共有多少种不同的铺法？ 输入格式 输入有多组，每组只有一个数 N，代表地板的长度 输出格式 对于每组数据，输出一个数，占一行，代表所有不同的瓷砖铺放方 ......

题目描述 如果将课本上的汉诺塔问题稍做修改：给定 N 只盘子，3 根柱子，但是允许每次最多移动相邻的 M 只盘子（当然移动盘子的数目也可以小于 M）, 最少需要多少次？ 输入格式 输入数据仅有一行，包括两个数 N 和 M（0<=M<=N<=8） 输出格式 仅输出一个数，表示需要移动的最少次数 #in ......

傻逼博客园，写好的文章不是自动保存在草稿箱，而是这个打开的网页。然后傻逼 Windows 自动更新使得断电退出这个网页，写的几百行文章没了。操了。 全路径计数 关于全路径计数，大前天 已经给出两例，今日再加一例。一般来说，点权和边权的做法是不一样的，所以分开来说。 全路径颜色统计（点权） https ......

区间DP 区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。 例题 石子合并 洛谷1880 #include<bits/stdc++.h> using namespace std; int n,i,j,k,l,ma,mi,a ......

树形DP 树形 DP，即在树上进行的 DP。由于树固有的递归性质，树形 DP 一般都是递归进行的。 例题 没有上司的舞会 洛谷1352 #include<bits/stdc++.h> using namespace std; int n,i,x,y,b[6005],f[6005][2]; vecto ......

状压DP 状压 DP 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。 例题 售货员的难题 洛谷1171 #include<bits/stdc++.h> using namespace std; int n,i,j,k,min1,a[25][25],f[1050000][25]; int ......

数位DP 数位是指把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是 0~9，其他进制可类比十进制。 数位 DP：用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征： 要求统计满足一定条件的数的数量（即，最终目的为计数）； 这些条件 ......

DP优化 单调队列优化 Watching Fireworks is Fun CF372C #include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,m,d,i,j,k,l,r,ma,f[2][150005],g[1 ......

背包DP 二进制分组优化 考虑优化。我们仍考虑把多重背包转化成 0-1 背包模型来求解。 预处理物品数量是2的次方。且要覆盖物品数量的点。即2 n次方+1到k index = 0; for (int i = 1; i <= m; i++) { int c = 1, p, h, k; cin >> p ......

线性DP 最长公共子序列 O(n*m)写法 int a[MAXN], b[MAXM], f[MAXN][MAXM]; int dp() { for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (a[i] == b[j]) f[i] ......

题目链接 [https://leetcode.cn/problems/maximum-subarray/description/](53. 最大子数组和 "https://leetcode.cn/problems/maximum-subarray/description/") 思路 分析动态规划题目 ......

题意（简化版） 给出一个长度为 $2n$ 的序列 $a_i$，求将序列分割为若干个长度为偶数的区间，满足每个区间内都不含绝对众数（出现次数严格大于长度的一半的数）的方案数。 $n\le 500000,,a_i\le2n$ 解法 解法和官方题解大致相同，虽然官方题解我也没看太明白（ 显然一定在偶数出断 ......

题目 D. Program 题意 给一个长度为n的‘+’，‘-’序列，表示+1和-1 在给m个查询，问忽略[l,r]之间的序列，能走到多少个不同的数字 思路 分为前后缀计算，前缀计算比较简单关键是后缀计算 后缀上，需要关注能够到达的最小值和最大值 定义sufL[i]和sufR[i]分别表示为到达的最 ......

树形DP 给出一棵树，要求以最少代价（或最大收益）完成给定的操作。 基本操作 树的遍历，用DFS从根节点开始进行记忆化搜索 从树最深处开始往回进行DP，用子节点dp值来更新父节点dp值 复杂度分析：遍历每个节点，总复杂度为$O(n)$ 例题 某大学有 $n$ 个职员，编号为 $1\ldots n$。 ......

描述 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能超过前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统，因此有可能不能拦截所有的导弹。怎么办呢？请帮助计算一下最 ......

描述 最近越来越多的人都投身股市，阿福也有点心动了。谨记着“股市有风险，入市需谨慎”，阿福决定先来研究一下简化版的股票买卖问题。 假设阿福已经准确预测出了某只股票在未来N天的价格，他希望买卖两次，使得获得的利润最高。为了计算简单起见，利润的计算方式为卖出的价格减去买入的价格。 同一天可以进行多次买卖 ......

博弈DP解决的是两人轮流操作，且没有平局的两人博弈游戏，和博弈问题的形式相同。 博弈论dp正推会有后效性,这是无法解决的 所以一般博弈论dp会选着逆推 但实际上逆推也不好写，所以这时候一般会以记忆化搜索dp的形式来写博弈论dp ......

所有代码的开头头文件，宏定义和命名空间如下 #include <bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define ll long long # ......

引入 按顺序排列的的三个矩阵 M1,M2,M3 计算三个矩阵相乘结果，有两种乘法 （M1 M2) M3 M1(M2 M3) 但两种乘法计算次数不同 三个矩阵维度如下 4 * 5 5 * 6 6 * 7 第一种计算次数 4 * 5 * 6 + 4 * 6 * 7 第二种计算次数 5 * 6 * 7 + ......

视频链接：https://www.bilibili.com/video/BV1EK411K7Eb/ #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N=1010; i ......

视频链接：https://www.bilibili.com/video/BV1KK4y1e7t7/ #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N=1010; i ......