直径meeting dp

定义一个序列是好的当且仅当其可以通过每次删去一对相邻的不同的数把序列删空。 给定一个长度为 $2n$ 的序列 $a$，求有多少种划分方式使得每一段都是好的。答案对 $998244353$ 取模。 $n \leq 5 \times 10^5$，时限 $\text{5.0s}$。 先考虑什么样的数列是合 ......

挺套路的 DP。 第一步是显然的：转换贡献体，DP 一条从 $(0,0)$ 到 $(n+1,n+1)$ 的路径，然后计算有多少个排列满足这条路径不经过任何一个 $(i,p_i)$。 正着统计肯定不好求，考虑容斥。即我们钦定一些路径上的点，满足这些点必须对应某个 $(i,p_i)$，然后计算有多少个 ......

P1140 相似基因 考虑如何设计状态。 设给出的两个串为串 $A$ 和串 $B$，长度分别为 $n$ 和 $m$。 我们用 $f[i][j]$ 来表示前 $i$ 个 $A$ 串碱基和前 $j$ 个 $B$ 串碱基得到的最大相似度。 我们因为求的是最大的相似度，而从题目给的表来看是可能为负的，所以先 ......

嘻嘻，农药打到钻石一了。😁 LCS https://atcoder.jp/contests/dp/tasks/dp_f 求两字符串 $s, t$ 的最长公共子序列。 $|s|, |t| \leq 3000$ 注意要求的不只是长度，如果要求长度就直接： 如果 $s_i = t_j$：$f_{i, j ......

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

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

题意 操作：每次可选一段区间覆盖为原区间最大值。 目标：$A$和$B$中相等的位尽量多。 思路 每个值只有为 $B_i$ 时才会贡献答案，设 $A_i$ 左边第一个为 $B_i$ 的为 $L_i$ ，同理右边的为 $R_i$，当然还要满足 $(L_i,i]$ 和 $[i,R_i)$ 的值均 $\le ......

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。 示例 :给定二叉树 1 / \ 2 3 / \ 4 5 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。 注意：两结点之间的路径长度是以它们之 ......

CF837D 考虑 $f[i][j][cnt2][cnt5]$ 统计前 $i$ 个数选 $j$ 个，满足有 $cnt2$ 个 $2$ 和 $cnt5$ 个 5 是否成立。 但 $f$ 只存 $0$ 或 $1$，考虑 $f[i][j][cnt5]=cnt2$，即统计前 $i$ 个数选 $j$ 个，满足 ......

Zero Remainder Sum 采用辅助数组 $ ndp[m + 1][\frac{m}{2}][k] $ 来求出每一行中在当前第 $ i $ 列，取了 $ j $ 个物品，总和模 $ k $ 的余数是 $ t $ 的最大和是多少。用 $ dp[n + 1][k] $ 来转移每一行的状态。 # ......

CF 1195C-Basketball Exercise 没怎么做过状态机 dp, 这个简单的题目甚至开始甚至搞出三维来。 #include <iostream> using namespace std; const int N = 1e5 + 10; typedef long long LL; / ......

挺小清新的一道计数题。 首先先分析下这个“最大前缀和”，按照最朴素的思路就是扫一遍每个前缀，然后记录一下当前的 $sum$ 与前面的 $mx$，但是如果你一直陷在这个思路上你就似了，因为按照这个思路做，你 DP 状态里需要记录 $sum$ 和 $mx$ 两个维度，算上下标一维总共是 $n^3$，并且 ......

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

题目链接 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 ......