chstor

线性DP

BFS(10) DFS(4) 二分答案(10) 前缀和(2) 排序算法(1) 树状数组(1) 模拟(1) 线段树(3) 背包DP(3) 蓝桥杯(4) 题解(13)

/ 注册

全部文章 / 线性DP （共8篇）

LCIS：最长公共上升子序列

LCIS：最长公共上升子序列法一：时间复杂度O(n^3) #include<bits/stdc++.h> using namespace std; #define mm(a,x) memset(a,x,sizeof a) #define mk make_pair #define...

2020-12-08

0 383

187. 导弹防御系统

187. 导弹防御系统代码如下： #include<bits/stdc++.h> using namespace std; #define mm(a,x) memset(a,x,sizeof a) #define mk make_pair #define ll long lon...

2020-12-07

0 513

P1020 导弹拦截

P1020 导弹拦截第一问：以后每一发炮弹都不能高于前一发的高度求最长不上升子序列长度，不再概述第二问：拦截所有导弹最少要配备多少套这种导弹拦截系统(最少需要几个最长不上升子序列) 法一：贪心从前往后遍历，取该值x,cnt表示子序列个数遍历所有（0~cnt-1）子序列，如果x大于当前...

2020-12-07

0 484

1285：最大上升子序列和

1285：最大上升子序列和最长上升子序列的长度转换为最大上升子序列的和代码如下: #include<bits/stdc++.h> using namespace std; #define mm(a,x) memset(a,x,sizeof a) #define mk ma...

2020-12-06

1 815

1263:友好城市

1263:友好城市北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同在保证任意两条航线不相交的情况下，被批准的申请尽量多题目分析：如图：最开始所有点为图1这种情况，我们需要处理不相交那么转换为图2，需要先把第一列数从小到大排列为了求得最多的情况，求第二列数的最长上...

2020-12-06

0 477

P1091 合唱队形

P1091 合唱队形求N-K的最小值，转换为求k的最大值与登山类似代码如下: #include<bits/stdc++.h> using namespace std; #define mm(a,x) memset(a,x,sizeof a) #define mk mak...

2020-12-06

0 442

1283：登山

1283：登山每次所浏览景点的编号都要大于前一个浏览景点的编号不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了题目分析：先登山后下山（不上山你怎么下山？）登山：求（1~n）的最长上升子序列下山：求（n~1）的最长上升子序列总路长为s上山+s下山-1 代码如下： #...

2020-12-06

1 1366

1286：怪盗基德的滑翔翼

1286：怪盗基德的滑翔翼初始时，可以选择任意一个点进行下降，可以选择一个方向逃跑（线性：左或者右），中途不改变方向求(1~n)：以a[i]结尾的最长上升子序列求(n~1): 以a[i]结尾的最长上升子序列最后，取最大值代码如下: #include<bits/stdc++.h&g...

2020-12-06

1 787