Harris-H

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

古老的牛市，遗迹的天梯 (DP)

古老的牛市，遗迹的天梯 (DP) 思路：,令表示到达第级阶梯的最小步数。因为题目保证阶梯高度递增，所以当然后根据题目还可以由中能够跳的转移过来。所以我们可以枚举起跳的点.然后转移，注意开始后退的点必须小于等于,因为如果开始后退的点比还大就肯定不是最优的，因为可以直接后退到点。时间复杂度： ...

2020-06-12

0 597

P4933 大师（DP)

P4933 大师（DP) 题意：给定序列求所有子序列中为等差数列的个数。(序列长度为1，2被认为是等差序列，空序列不是等差序列)。思路：很巧妙的,因为,数字较小。所以考虑设表示以下标的数字结尾公差为的等差序列个数。因为公差可能为负，所以整体向右移动位。状态转移方程：. 这个是当两个数组成的等差序...

2020-06-09

1 652

最长递增子序列的三种解法（LIS）

最长递增子序列的三种解法（LIS） 1.用LCS(求LIS) 时间复杂度O(n^2) 思路：将原序列a排序后产生一个新的序列b，比较a和b最长公共子序结果就是LIS. #include<bits/stdc++.h> using namespace std; const ...

2020-05-01

0 1159

Nowcoder practice 60 C.操作集锦

Nowcoder practice 60 C.操作集锦 #include<bits/stdc++.h> using namespace std; #define ll long long const int mod=1e9+7; int dp[1010][1010][27];//d...

2020-05-01

0 644

AtCoder Beginner Contest 160-F - Distributing Integers（DFS&DP)

AtCoder Beginner Contest 160-F - Distributing Integers（DFS&DP) 题目传送门 #include<bits/stdc++.h> using namespace std; typedef long long ll; c...

2020-05-01

0 897

POJ-3264 Balanced Lineup （RMQ)

POJ-3264 Balanced Lineup （RMQ) 题目传送门题意：给定若干区间查询最值之差。 #include<iostream> #include<cstdio> using namespace std; const int N=5e4+5; int dp...

2020-05-01

0 534

HDU 3193-Find the hotel (RMQ)

HDU 3193-Find the hotel (RMQ) 题目传送门题意：找到所有满足（不存在比该酒店价格和距离都低的其他酒店）这样的酒店。思路：即价格大于等于它的酒店不用考虑，只用考虑价格比他小的酒店当中是否距离最小的那个比它的距离大。若存在一个即该酒店满足。最后排序。 #includ...

2020-05-01

0 596

Codeforces Round #630 (Div. 2) D. Walk on Matrix （思维&DP）

Codeforces Round #630 (Div. 2) D. Walk on Matrix （思维&DP）题目传送门题意：给定用DP计算的矩阵错误异或和与正确异或和的差值，构造这样一个矩阵。思路：显然对于&运算DP的方法是错的，因为前一个状态的最优&当前位置...

2020-05-01

1 726

AtCoder Grand Contest 043 A - Range Flip Find Route（路径DP）

AtCoder Grand Contest 043 A - Range Flip Find Route（路径DP）题目传送门题意：给H * W黑白矩阵，求从（1，1）走到（H,W）路径全为白的最小翻转次数（可对小矩形进行翻转–（黑变白）（白变黑））与路径DP类似，只是加了个判断：如果当前...

2020-05-01

0 1016

P1057 传球游戏（DP）

P1057 传球游戏（DP）题目传送门题意：n个人传球，求从1开始传，传m次传给1的方案数。思路： AC代码： sol1：取模的方法： #include<cstdio> int a[35][35]; int main(){ int n,m; scanf("...

2020-05-01

0 587