这里是关于序列型动态规划的题目以及程序
序列型动态规划
拦截导弹
题目描述 Description
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。
输入描述 Input Description
输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数)
输出描述 Output Description
输出这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
样例输入 Sample Input
389 207 155 300 299 170 158 65
样例输出 Sample Output
6
2
数据范围及提示 Data Size & Hint
导弹的高度<=30000,导弹个数<=20
The Code Of My Program
1 | /********************* |
最长严格上升子序列
题目描述 Description
给一个数组$a_1, a_2 … a_n$,找到最长的上升降子序列$ a_{b_1} < a_{b_2} < .. < a_{b_k}$,其中$ b_1 < b_2 <… < b_k$。
输出长度即可。
输入描述 Input Description
第一行,一个整数$N$。
第二行 ,$N$个整数$(N \leq 5000)$
输出描述 Output Description
输出$K$的极大值,即最长不下降子序列的长度
样例输入 Sample Input
5
9 3 6 2 7
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
【样例解释】
最长不下降子序列为3,6,7
The Code Of My Program
1 | /********************* |
线段覆盖2
题目描述 Description
数轴上有$n$条线段,线段的两端都是整数坐标,坐标范围在$0$ ~ $1000000$,每条线段有一个价值,请从$n$条线段中挑出若干条线段,使得这些线段两两不覆盖(端点可以重合)且线段价值之和最大。
输入描述 Input Description
第一行一个整数$n$,表示有多少条线段。
接下来$n$行每行三个整数,$ \; a_i \; b_i \; c_i \; $,分别代表第$i$条线段的左端点$a_i$,右端点$b_i$(保证左端点<右端点)和价值$c_i$。
输出描述 Output Description
输出能够获得的最大价值
样例输入 Sample Input
3
1 2 1
2 3 2
1 3 4
样例输出 Sample Output
4
数据范围及提示 Data Size & Hint
数据范围
对于$40\%$的数据,$n\leq10$;
对于$100\%$的数据,$n\leq1000$;
$0<=a_i,b_i<=1000000$
$0<=c_i<=1000000$
思路:如果不是线段而是点,显然这题很容易就能解决。于是我们把每个线段都看成一个点,则记选至第i个线段时的最大价值为f[i],j为不与i相覆盖的且在i之前的线段(当然,如果要从左往右推的话,这里要事先让线段按右端点排序,因为这样可以使左边尽可能地多使用线段),则有DP方程f[i]=max(f[i],f[j]+seg[i].c),初始化f[i]=seg[i].c,最后遍历所有f[i]取最大值即可
The Code Of My Program
1 | /********************* |