工大最菜

dp

01规划(3) ACM比赛总结(3) ACM训练日记(11) bfs(7) dfs(5) Dilworth定理(1) exgcd(1) gcd(2) java(1) KM(1) kmp(4) map(4) MOD运算(1) os(3) rmq(1) set(2) STL的操作(1) __int128(1) 一般图带花树的最大匹配(2) 三分(2) 中位数(1) 主席树(6) 二分(8) 二分图匹配(9) 二分图最大匹配(1) 二分图的多重匹配(1) 二维偏序(2) 二进制(2) 优先队列(2) 倍增DP(2) 其他(1) 分块(11) 分层图最短路(1) 分治(5) 分组背包(3) 前缀和(6) 动态最短路(1) 区间dp(18) 单调队列(2) 单调队列dp(2) 博弈论(11) 双连通(5) 同余最短路(1) 后缀和(1) 后缀数组(2) 因数(1) 大整数(1) 大模拟(2) 字典树(1) 字符串哈希(16) 完全背包(1) 容斥(1) 尺取(4) 并查集(3) 序列自动机(2) 康托展开(1) 异或(4) 强连通(1) 思维(6) 扩展KMP(3) 扫描线(2) 技巧(11) 拉格朗日插值法(1) 拓扑排序(3) 数位dp(8) 数学推导(2) 数论(18) 整体二分(2) 暴力(6) 最大权闭合子图(1) 最小生成树(5) 最小表示法(1) 最短路(15) 未归档(2) 构造(2) 构造树(1) 染色问题(1) 树(9) 树dfs序(2) 树上分块(2) 树上启发式合并(6) 树上差分(2) 树形dp(16) 树状数组(3) 树的BFS序(1) 树链剖分(6) 概率(24) 模拟退火(6) 欧拉函数(3) 欧拉回路(4) 点分治(5) 状压dp(11) 珂朵莉树(2) 生成函数(4) 矩阵快速幂(3) 矩阵计数(1) 离散数学(1) 离线(1) 线性基(1) 线性规划(1) 线段树(18) 线段树合并(2) 组合数学(1) 组合计数(1) 网络流(14) 莫比乌斯反演(1) 莫队(6) 表达式求值(1) 计数(5) 计算几何(4) 调度问题(1) 贪心(8) 费用流(6) 费用背包(1) 递归(2) 长链剖分(1) 题解(14)

/ 注册

全部文章 / dp （共80篇）

牛客小白月赛19 J-「火」皇家烈焰与前后状态有关的四维dp的降维

题目链接：https://ac.nowcoder.com/acm/contest/2272/J 题目大意：我的思路是用f[i][j][k][w]:表示前i个格子 j：前一个格子有没有 k：这个格子有没有 w：下一个格子有没有的情况数。状态表示冗余了。我们用f[i][j][k]表示前i个格子...

2019-11-24

0 386

codeforces. 756 B. Travel Card 多选择的dp+二分转移

题目链接：https://codeforces.com/problemset/problem/756/B 题目大意：票价按以下方式构造。门票分为三种：一张单程票要花20卢布，一张90分钟的票需要50卢布，一天（1440分钟）的票需要花费120卢布。请注意，在时间t激活的x分钟的票证可用...

2019-11-23

0 479

codeforces 766 C. Mahmoud and a Message dp字符串的分割

题目链接：https://codeforces.com/contest/766/problem/C 题目大意：给出一串有小写字母组成的长度为n的字符串。每个小写字母都有对应值ai，分割原串，要求对应值为ai的字符不能出现在长度超过ai的字串中。问共有多少种分割方式，分割后会出现的最长子串长度是多少，...

2019-11-23

0 769

codeforces 1051 D. Bicolorings 两行的颜色块作为状态的计数dp

题目链接：https://codeforces.com/problemset/problem/1051/D 题目大意：有两行格子长度为n，每个格子可以涂成白色或者黑色。如果两个格子颜色相同并且相邻那他们就属于同一个联通块。现在问你有多少中涂色方案使联通块=k mod=998244353。思路...

2019-11-21

0 432

codeforces 1253 E - Antenna Coverage DP区间覆盖的最小扩展次数

题目链接：https://codeforces.com/contest/1253/my 题目大意： m个天线，每个天线的位置是xi，分数是si,覆盖范围是[xi−si;xi+si],每个硬币可以使一个天线的si+1，求覆盖整个[1;m]的最少硬币思路： #include <bits/...

2019-11-17

0 830

1256 E-Yet Another Division Into Teams 划分组-dp

题目链接：https://codeforces.com/contest/1256/problem/E 题目大意：有n个人，每个人有一个能力，现在让你分组。每组至少3个人。团队的多样性是这个团队的：最大能力-最小能力。总的多样性：所有团队的多样性的和。让你分组：使总多样性最小。我们尽量让能力...

2019-11-05

0 462

codeforces 1221D - Make The Fence Great Again 左右格子高度不同的最小费用dp

题目链接：http://codeforces.com/problemset/problem/1221/D 题目大意： q个询问。每次询问给你n个高度为a[i]的栅栏。升高第i个栅栏高度1将花费b[i]。现在要让所有的栅栏高度和相邻栅栏的高度都不同。问最小的费用是多少。思路：由题意可以知道：每个栅...

2019-10-24

0 538

codeforces 339 C. Xenia and Weights 三维dp

题目链接：http://codeforces.com/contest/339/problem/C 题目大意：在天平上放砝码你要在左边放一下然后到右边放一下一直重复这样放m次每次你放在其中一边都要让另外一边的重量比你少你可以用1~10中的某些砝码问你要怎样放才行,或者告知系统不能放m次 ...

2019-10-24

0 451

codeforces 919 D. Substring - 拓扑排序 + dp图上最长路

题目链接：http://codeforces.com/problemset/problem/919/D 题目大意：给你一个n点m条边的有向图。每个点有一个字符。一条路的权值为这条路上所以字符出现次最大的那个字符的次数。可能有重边，有自环。可能不连通。求所有路的最大权值。如果可以为无穷大，输出-1...

2019-10-23

0 509

codeforces 913C. Party Lemonade 二进制记忆化搜索

题目链接：http://codeforces.com/contest/913/problem/C 题目大意：有n瓶柠檬水。第i瓶的容量为2^(i-1)。价格为ai。问现在需要买容量>=L的柠檬水。问至少需要多少钱。思路：我们考虑把L拆成二进制。对于第5为1。那么买>=L的容量的水...

2019-10-21

0 402