HerioOvO

DP

BFS(5) CF题解(3) DFS(20) LCA(2) Leetcode(1) Nowcoder题解(4) ST(1) Tarjan(1) 二分(4) 二分法(1) 二叉树题目(4) 位运算(2) 前缀和(4) 博弈论(3) 图论(1) 字符串(5) 学习笔记(1) 并查集(2) 快速幂(1) 思维(7) 排序(1) 数状数组(3) 数论(20) 暴力(5) 最短路(5) 未归档(5) 标记处理(1) 栈(1) 概率论(1) 模拟(2) 浮点数(1) 生成树(4) 算法(5) 素数筛(3) 线段树(6) 组合数学(8) 蓝桥杯(1) 计算几何(1) 贪心(26) 递推(3) 题解(3) 高精度(2)

/ 注册

全部文章 / DP （共20篇）

ABC - 162 - F - Select Half (DP&奇偶性）

ABC - 162 - F - Select Half (DP&奇偶性）题目传送门思路： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+5; ll ...

2020-05-01

0 547

P2858 [USACO06FEB]Treats for the Cows G/S （区间DP)

P2858 [USACO06FEB]Treats for the Cows G/S （区间DP) 题目传送门思路： AC代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const in...

2020-05-01

0 508

P3146 [USACO16OPEN]248 G （区间DP）

P3146 [USACO16OPEN]248 G （区间DP）题目传送门思路： AC代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=300; int a[N...

2020-05-01

0 588

P1091 合唱队形 (DP&LIS)

P1091 合唱队形 (DP&LIS) 题目传送门思路：显然正反跑两边LIS，遍历一遍取最值即可。时间复杂度：O（n^2) 不过可以用upper_bound()压到O(nlogn)这里就不写这种做法了。。。。 AC代码： #include<bits/stdc++.h> ...

2020-05-01

0 538

「木」迷雾森林 (路径DP）

「木」迷雾森林 (路径DP）题目传送梦思路：板子题，唯一需要注意的是数据较大要用到快读。 AC代码： #include<bits/stdc++.h> using namespace std; const int mod=2333,N=3e3+5; int m,n; int a...

2020-05-01

0 531

G - 免费馅饼 (DP&数塔）

G - 免费馅饼 (DP&数塔）思路：从最大时间开始倒序DP，状态转移即由前一时刻周围的三个位置得到。具体看代码。PS：一开始看成1e6，已知MLE。 AC代码： #include<cstdio> #include<algorithm> #include<...

2020-05-01

0 424

P1004 方格取数 (双状态DP&四维DP）

P1004 方格取数 (双状态DP&四维DP）题目传送门思路：由于两个路径的最优值会互相影响，所以同时走选择最优方案才是正确解法，这样保证不会将一个数加两遍。若走两遍可能不是最优方案（因为第一次会影响第二次的方案）复杂度O(9^4)还是很小的。因为是滚动数组，所以可以降到三维，但没必...

2020-05-01

0 579

P1006 传纸条 (双状态DP）

P1006 传纸条 (双状态DP）题目传送门思路：与P1004类似，也可以用四维，不过可以用三维记录步数即可完成状态转移。具体看代码。四维AC代码： #include<cstdio> #include<algorithm> using namespace std...

2020-05-01

0 586

J - Staircases （递推&数的划分）

J - Staircases （递推&数的划分）题意：求有多少种不同数之和为n的方案。(划分个数大于1）思路： AC代码： #include<cstdio> #include<cstring> using namespace std; const int...

2020-05-01

0 487

I - Palindrome（LCS&字符串)

I - Palindrome（LCS&字符串) AC代码： #include<cstdio> #include<cstring> #include<algorithm> #include<string> #include<iost...

2020-05-01

0 534