小毅儿

DP

BFS(1) DFS(4) Huffman树(1) 动态规划(4) 埃氏筛(3) 数论(2) 最短路&&最小生成树(11) 未归档(24) 模版专项(9) 矩阵快速幂(3) 笔记(2) 笔记（STL）(5) 笔记（博弈）(1) 笔记（字符串）(8) 笔记（定义最大数）(1) 笔记（并查集）(2) 笔记（排列组合）(2) 笔记（结构体）(2) 笔记（范围问题）(1) 笔记（贪心）(1) 笔记（高精度）(6) 线性基(1) 组合数学(11) 题解(34)

/ 注册

全部文章 / DP （共5篇）

滑雪（POJ 1088）（DP+搜索+二维最长下降子序列）

试题链接：https://vjudge.net/problem/POJ-1088 这道题肯定最先想到是DFS跟BFS，但是数据是100*100，还要每个点都进行搜索，肯定会超时。但是我为了巩固DFS跟BFS，把这道题的BFS跟DFS都码了一遍，如果这道题数据没有这么大的话，肯定是可以的。下面的代...

2020-04-09

0 549

最长公共子序列

题目链接：POJ 1458 #include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include &l...

2020-04-05

0 445

区间dp

问题链接：http://acm.upc.edu.cn/OnlineJudge/problem.php?cid=1008&pid=0 这是一个经典题目"凸多边形最优三角形剖分",解法是区间dp。 dp[i][j] 表示从第i到第j个点最优剖分的答案。当 j=i 或 j=...

2020-03-09

0 525

DP之LIS（最长上升子序列）

试题链接：最长上升子序列：POJ 2533如何把这个问题分解成子问题呢？“求序列的前n个元素的最长上升子序列的长度F(n)”是一个子问题，但这样分解子问题，不具有“后无效性”。假设F(n)=x，但可能有多个序列满足F(n)=x。有的序列的最后一个元素比小，不能和形成一个更长的上升子序列······以...

2020-02-12

1 671

双线程DP

求从N*M矩形的左上角到右下角两条路径的最大值下面的代码中：a[i][j]代表：任意一点的路程b[i][j][k][l]代表：一点在i,j处，另一点在k,l处时所能取得的最大值 #include <cstdio> #include <iostream> #include &l...

2020-02-12

0 540