Cruiying

dp

2-sat(1) BSGS(2) dfs(2) dp + 线段树(1) floyd(3) Hash(1) KM算法(1) Kruskal重构树(2) LCA(6) manachar(2) Mendix(4) tarjan(1) 中位数(1) 主席树(2) 二分(3) 分数规划(3) 前缀和优化dp(2) 单调栈(6) 单调队列(1) 单调队列优化dp(1) 博弈(2) 后缀数组(15) 字典树(1) 差分约束系统(1) 并查集(4) 异或(2) 思维(2) 思维题(4) 扩展欧几里得算法(1) 拉格朗日插值(2) 数论(8) 未归档(15) 构造(1) 枚举(1) 模拟(3) 模板(1) 水题(4) 矩阵加速(2) 线段树(3) 网络流(2) 莫比乌斯反演(2) 莫队(4) 蓝桥杯(1) 规律(2) 贪心(2) 输入输出(1) 题解(1)

/ 注册

全部文章 / dp （共63篇）

CF 219D(树形dp)

题意：给一个树形图(有向树)，n个节点，n-1条有向边，要求选一个节点作为根，使需要改变方向的边的数目最少。并输出所有可能作为根的点。设dp[i]表示以i为根，需要改变多少个边方向题解：首先dfs从下向上dp[i],然后在dfs一次从上更新dp[i] #include <bits/stdc...

dp

2019-10-11

0 702

CF 463D (DP 或者偏序)

给你k个长度为n的排列，求这些排列的最长公共子序列的长度题解：k个都是一个排列，所以，每一个数在自己的的排列中只会出现一次，所以，我们可以记录每一个数在k个排列中的位置，然后就变成了k维偏序问题，a[i] <= a[j] #include <bits/stdc++.h> usi...

dp

2019-10-11

0 525

CF 448C - Painting Fence(dp待看)

题意：你面前有宽度为1，高度给定的连续木板，每次可以刷一横排或一竖列，问你至少需要刷几次。思路：先逆推，dp[i][j]表示第i列以后的木板都刷完了（不包括第i列）且前面的第j列是横着刷的（且假设它能够刷到后面的第i+1列），那么第i列之后不包括第i列最少需要的次数。所以当value[j]>...

dp

2019-10-11

0 674

P4170 [CQOI2007]涂色(经典区间dp)

假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBG...

dp

2019-10-10

0 810

CF1114D Flood Fill(经典区间dp)

n 个方块排成一排，第 i 个颜色为 ci。定义一个颜色联通块 [l,r] 当且仅当 l 和 r 之间（包l,r）所有方块的颜色相同。现在你可以选定一个起始位置 p，每次将 p 所在颜色联通块的所有方块颜色改成另一种。这个操作可能将多个颜色联通块合并成一个。问最少要多少步，能让 [1,n] 变成一个...

dp

2019-10-10

0 591

CF607B Zuma(dp好题)

给出n个数字，我们来逐步删除，如果一个子串是回文数，就可以直接删除，问删除完最少的次数。设dp[i][j]为删除区间[i,j]所需最小次数题解：记忆化搜索 #include <bits/stdc++.h> using namespace std; const int maxn = 50...

dp

2019-10-08

0 616

CF983B XOR-pyramid(区间dp)

设f[i][j]为第i层的第j个数，可得 f[i][j] = f[i - 1][j - 1] ^ f[i - 1][j] #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn ...

dp

2019-10-08

0 486

CF580D Kefa and Dishes(状态压缩dp)

kefa进入了一家餐厅，这家餐厅中有n个菜（0<n<=18）,kefa对第i个菜的满意度为ai（0<=ai<=10^9），并且对于这n个菜有k个规则，如果kefa在吃完第xi个菜之后吃了第yi个菜（保证xi、yi不相等），那么会额外获得ci（0<=ci<=10^9...

dp

2019-10-08

0 428

cf358D. （dp好题）

题意：给你两个字符串s 和 t ，然后在s中找k个不重叠的子串，并且能够在t中按顺序能找出这k个子串，求这k个子串的最大长度和 dp[i][j][t][0] ，i是在s中的位置， j是在t中的位置，i，j跟求最大公共子串一样， t是当前子串的个数， 1说明还能继续匹配子串个数不用加， 0说...

dp

2019-09-30

0 528

A. Writing Code（dp二维完全背包）

有n个人，要写m行代码，第i个人每写一行会出现ai个bug，每个人可以写任意行，但总bug数不能超过b个，求总方案数 dp[j][k] 表示有j行代码k个bug的方法数,所有转移方程为：类似一维完全背包dp[j + 1][k + a[i]] += dp[j][k] #include <bit...

dp

2019-09-29

0 514