工大最菜

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

dp专题丢失阵列(组合数dp)

题目链接：http://codeforces.com/problemset/problem/1105/C 题目大意：给你一个n, l, r; 让你构造阵列满足以下条件：阵列长度为n；阵列中所有的整数位于[l, r]之间这个阵列所有的整数和能被3整除让你求有多少个构造方...

2019-01-23

0 480

dp专题公平的坚果和字符串（类似跳台阶dp）

题目链接：http://codeforces.com/contest/1084/problem/C 对于一个由小写拉丁字母组成的字符串s，坚果想找到严格增加的序列p1，p2，…，pk的数量，保证：对于每个i（1≤i≤k），spi =‘a’。对于每个i（1≤i<k），存在pi <j ...

2019-01-09

0 397

dp专题可行方案总数：以01背包为例

我们在面对这个相同条件但所求结果不同的问题中设f[i][j]为前i件物品组合出来的容量为j的方案数（可以优化成一维） //无优化： #include<bits/stdc++.h> using namespace std; int a[105]; int dp[100][10...

2019-01-09

0 459

dp专题 0-1背包输出具体的方案

0-1背包的状态转移方程： dp[i][j]=max(dp[i-1][j], dp[i-1][j-a[i]]+a[i]); 如果一个物品被选中那么： dp[i][j]==dp[i-1][j-a[i]]+a[i] dp[i][ans-a[i]]+a[i]==ans//ans初始值：dp[n][s]表...

2019-01-09

0 682

dp专题神奇的口袋

有一个口袋容积为m，有n个物品，题目的体积为a1,a2,a3…an。把m装满有多少种不同的装法。递归： int dfs(int n, int m)/*从n个物品中选出总体积为m的选法*/ { if(m==0) return 1; if(n<=0) ...

2019-01-07

0 392

dp专题滑雪

求一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。最长的滑坡 dp[i][j]表示从i，j出发的最长的滑坡递推的顺序：由高度从低到高，因为要知道dp[i][j]，必须知道周围所有比自己矮的dp值。记忆化递归：可以不按从低到高的顺序直接递归。人人为我：dp[i...

2019-01-07

0 934

dp专题最佳加法表达式

在n个数字中插入m个加号使表达式的值最小 num[i][j]:位置i到位置j的所表示的数字。递推： dp[m][n]表示在n个数字中插入m个加号所能形成的表达式最小值边界条件：dp[0][i]=num[1][i] 递推公式：dp[i][j]=min(dp[i-1][k]+num[k+1][j]...

2019-01-06

0 436

dp专题最长公共子序列

dp[i][j]表示a字符串前i个字符和b字符串前j个字符的最长公共子序列 if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i]p[j-1], dp[i-1][j]); 边界条件： dp[i][0]=0;(0<=i...

2019-01-06

0 380

dp专题最长上升子序列

dp[i]表示第i个数字为结尾的最最长上升子序列长度 dp[i]= max(dp[j]+1:(ai>aj&&k!=1), dp[i]) 边界条件：d[i]=1 （1<=i<=n） #include<bits/stdc++.h> using names...

2019-01-06

0 417

dp专题最大子段和

``给你一个序列，求它的最大子段和 dp[i]表示以第i个数字为结尾的最大子段和 dp[i]=max(dp[i-1]+a[i], a[i]); 边界条件：dp[0]=0; #include<bits/stdc++.h> using namespace std; int a[20...

2019-01-06

0 467