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篇）

CF946D (思维 + 分组背包 + dp)

题目大意：给出n行m列01串，对于每一行所要花费的代价是行中第一个1和最后一个1之间的距离加一，现在你有魔法可以去除掉k个1，问去掉不多于k个1的情况下，你所能获得的最小代价是多少。题解：每一天翘多少课所得到的价值都是互相独立的，那么就很容易想到将每一天都看成一个物品组，翘不同数量的课可以达到不同...

dp

2019-08-20

0 526

CF1016C (前后缀 + 思维题）

题意：给一个2n的矩阵，每一个点有一个权值，从左上角出发，时间t=0开始，连续的走，将矩阵走完，每走一步，t++,并且得到t当前格子的权值的值，问如何走，使得最走完得到的最大权值和是多少。不难发现方案一定是先走一个S形，再直着走到头，再走回来。 #include <bits/stdc++.h...

dp

2019-08-17

0 480

CF1153D (树形dp + 思维 + 贪心)

n个节点以1为根的一棵树，每个非叶子节点都有一个操作max或min（0表示min，1表示max），表示这个节点中的值应该分别等于其子节点中所有值的最大值或最小值。假设树上有k个叶节点，你可以将每个叶节点填上[1,k]的数字，且每个数字只使用一次，求根节点的最大值题解：树形dp 可以看出来是个树形d...

dp

2019-08-15

0 462

CF1083A(树形dp)树上最长路径

题意：点有正权，边有负权。在这样的无根树中找到一条权重最大的链并输出权重(树上最长路径) 题解：将无根树转为有根树，我们把1当做根dp[u]表示节点u开始，子树先得最长路径转移方程为：dp[u] = max(dp[u], dp[to] + a[u] - edge[i].w)对于每一个子树，找到最长...

dp

2019-08-14

0 494

CF375B (dp)

题目描述: 给你一个0、1组成的矩阵，大小为 n × m ，你可以把任意的两行的位置相互交换，请你给出变换后能得到的最大子矩阵，满足只由“1”组成。输入: 第一行给出两个整数 n 和 m (1 ≤ n, m ≤ 5000)。接下来 n 行每行给出两个给出一个矩阵a，仅有0、1组成，中间没有间隔。...

dp

2019-08-02

0 440

CF721C Journey（SPFA + dp）

给出一个n个点m条边的有向无环图。问从1到n，在距离不超过k的情况下最多经过多少点，并输出一个方案。 SPFA + dpdp[i][j]表示第i个点经过j条边的最小值然后二维标记，直接跑SPFA #include <bits/stdc++.h> using namespace std...

dp

2019-08-02

0 606

多校（第五场）T2（十进制求广义斐波那契）好题

You are given four positive integers x0, x1, a, b. And you know xi=a⋅x(i−1)+b⋅x(i−2) for all i≥2. Given two positive integers n, and MOD, please calcu...

dp

2019-08-01

0 513

CF 407B. Long Path（dp好题+思维）

题目大意：有n+1个房间。从1-n个房间。每个房间有两扇门。一扇去i+1的房间另一扇去编号为pi的房间。问到达n+1的房间至少要走多少次。如果走过的次数是奇数次：就走pi这个门如果走过的次数是偶数次：就走i+1这个门（初始值1的位置是奇数）dp[i] 表示1到i这个位置需要走多少次门思路：因为 1 ...

dp

2019-07-31

0 592

CF225C Barcode（dp好题）

给你一个NM的矩阵，其中有白色和黑色两种颜色，我们可以将其中的任意格子颜色变成另外一种颜色，问最少操作多少次（变换颜色），使得这个NM的矩阵变成一个条形码，并且保证相同颜色挨在一起的列数不小于x不大于y、（条形码|||||||） dp[i][0]表示以0为结尾合法的最小染色数dp[i][1]表示以1...

dp

2019-07-30

0 484

CF577B (抽屉原理+01背包)

给出 1个长度为 n 的序列，以及 1 个正整数 m。问这个原序列中是否存在非空子序列，使其元素之和能被 m 整除。把多于n+1个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件。代入本题中我们可以发现，当得到这个序列的n个前缀和%m时，一定会出现两个相同的数，这两个前缀和相减得到的序列和...

dp

2019-07-30

0 702