工大最菜
工大最菜
全部文章
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)
归档
标签
去牛客网
登录
/
注册
liweihang的博客
全部文章
/ dp
(共80篇)
dp专题-UVA - 1347-双调欧几里得旅行商问题-不重复的来回路径问题
题目大意: 双调欧几里得旅行商问题(动态规划) 给定平面上n(n≤1000)个点的坐标(按照x递增的顺序给出。各点x坐标不同,且均为 正整数),你的任务是设计一条路线,从最左边的点出发,走到最右边的点后再返回,要求 除了最左点和最右点之外每个点恰好经过一次,且路径总长度最短。两点间的长度为它们的 欧...
2019-06-15
0
770
dp专题-UVA - 437-DGA上的dp-立方体堆积求最大高度
题目链接:http://fastvj.rainng.com/contest/306591#problem/B 题目大意: 有n(n≤30)种立方体,每种都有无穷多个。要求选一些立方体摞成一根尽量高的柱子 (可以自行选择哪一条边作为高),使得每个立方体的底面长宽分别严格小于它下方立方体 的底面长宽。 ...
2019-06-15
0
463
dp专题-UVA - 1025-城市里的间谍-时间线作为序
题目链接:http://fastvj.rainng.com/contest/306591#problem/A 题目大意: 某城市的地铁是线性的,有n(2≤n≤50)个车站,从左到右编号为1~n。有M1辆列车从 第1站开始往右开,还有M2辆列车从第n站开始往左开。在时刻0,Mario从第1站出发,目的...
2019-06-15
0
592
dp专题-DGA上的dp:硬币问题-完全背包:回溯路径+记录路径
题目:硬币问题。有n种硬币,面值分别为V1, V2, …, Vn,每种都有无限多。给定非负整数S, 可以选用多少个硬币,使得面值之和恰好为S?输出硬币数目的最小值和最大值。 1≤n≤100,0≤S≤10000,1≤Vi≤S。 分析:这个模型和上一题类似,但也有一些明显的不同之处:上题并没有确定路径...
2019-06-14
0
532
dp专题-DGA上的dp-最长路:矩阵嵌套
题目大意: 描述 有n个矩形,每个矩形可以用a,b来描述,表示长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a<c,b<d或者b<c,a<d(相当于旋转X90度)。例如(1,5)可以嵌套在(6,2)内,但不能嵌套在(3,4)中。你的任务是选出尽可能多的矩形排成一...
2019-06-14
0
552
0-1背包-变形
题目链接:https://ac.nowcoder.com/acm/contest/642/D 题目大意: 思路:一开始想的是,01背包dp出dp[n][s-1]。然后标记选的音乐,从没有标记的音乐找到MAX,输出:dp[n][s-1]+MAX; 然后WA了, 想到一个错误样例: 1 5 7 6...
2019-04-21
0
558
dp专题+通信系统dp记录状态
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1069 题目大意: 题意分析: 题目本身描述得比较绕口,这里利用题目给的测试用例的输入描述一下: 生产的 厂家m1 厂家m2 厂家m3 ...
2019-02-17
0
336
dp专题+箱子堆积(最大递减序列变形)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1069 题目大意:把给定的长方体(不限)叠加在一起,叠加的条件是,上面一个长方体的长和宽都比下面长方体的长和宽短;求这些长方体能叠加的最高的高度.(其中(3,2,1)可以摆放成(3,1,2)、(2,1,3...
2019-02-16
0
558
dp专题+最大子矩阵
题目链接:http://poj.org/problem?id=1050 题目大意:求一个最大为100*100矩阵中的子矩阵中元素之和的最大值。 枚举此子矩阵是第i行到第j行。然后压成一维dp最大子段和。 #include <iostream> #include <stdio.h...
2019-02-16
0
358
dp专题 字符串转化
题目链接:https://www.luogu.org/problemnew/show/P2758 题目大意: 设A和B是两个字符串。我们要用最少的字符操作次数,将字符串A转换为字符串B。这里所说的字符操作共有三种: 1、删除一个字符; 2、插入一个字符; 3、将一个字符改为另一个字符; !皆为小写字...
2019-01-25
0
520
首页
上一页
1
2
3
4
5
6
7
8
下一页
末页