这是一道动态规划题,和昨天的取硬币还有最长公共字串有点类似。
 
1.题目描述:
      
                  某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高                 度。某 天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式一行,为导弹依次飞来的高度。

输出格式两行,分别是最多能拦截的导弹数与要拦截所有导弹最少要配备的系统数。

2.样例输入

300 207 155 300 299 170 158 65

3.样例输出
            6

2

4.算法思想:
            我们遇到这道题目,我们自己算的话就是,先从300开始,然后比较207比300小能拦截,155比207小能拦截,65比155小能拦截,这一趟是能拦截4 个导弹。然后暴力求出每次最多能拦截的导弹数,再比较最大的,这是我们平时的暴力破解思维。但是,这样想想要多少次循环,也太麻烦了。当然最后最多能拦截的是300 300 299 170 158 65这六种。我们应该想到动态规划,动态规划只是一种工具。这道题目怎么用到动态规划呢?动态规划其实就是填矩阵,之前在别的博客上看到求最长子序列的时候填的是二维数组,当然这题也一样是。怎么填呢?在求最长公共子串时从头开始遍历,如果想等,则加1,不等则继续是这个,这道题目呢如下,动态规划要从底部开始动态规划。
  300   207   155   300  288  299   170   158   65
    6      4        2      5       4      4         3      2     1
刚开始一直没有思路,但是仔细想一下,发现我300比207大,最大序列加一,207比155大加1,但是300不比155大,这时候怎么办,就要递归遍历。但是我从末尾看,只要65是1个长度,只要158大于65,那么158肯定是第二个长度,170大于158,是第3个长度,299大于170,第4个长度,但是288没有299大,前面比较,比170大,所以等于170的长度+1。300比299大,所以长度等于299的长度+1,155比65大,所以155等于65的长度+1,这就得到了状态转移方程。动态规划问题,不管是不是上升序列,都要进行判断,这道题呢是怎么判断的?这个导弹和之前的导弹比较,如果这个导弹比大于之前的并且它的temp值也是最大的,保存这个下标,然后让temp[k] = temp[z] + 1,即得到了最后的结果,所以一定要搞清楚动态规划转移方程。

具体代码示例

package 蓝桥杯;
/*
* 300 207 155 165 288 299 170 158 65
5 4 2 3 4 4 3 2 1
*/
public class 导弹问题 {
static int weizhi[] = {500,700,300,207,155,165,288,299,170,158,65};
public static void main(String[] args) {
//记录最大的位置 int temp[] = new int[weizhi.length];
temp[weizhi.length-1] = 1;
f(temp,weizhi.length-2); //从第7个位置开始
for(int i=0;i<weizhi.length;i++) {
System.out.println(temp[i]);
}
} private static void f(int[] temp, int k) {
if(k==-1) {
return;
} int max=0;
int z = 0;
for(int i=k+1;i<=weizhi.length-1;i++) {
if(weizhi[i]<weizhi[k]) {
if(temp[i]>max) {
max = temp[i];
z = i;
}
}
temp[k] = temp[z]+1;
f(temp, k-1);
}
}
}
05-11 22:19