首页 > 代码库 > Hdu 1257 最少拦截系统
Hdu 1257 最少拦截系统
Problem地址：http://acm.hdu.edu.cn/showproblem.php?pid=1257
以前做过拦截导弹的简单题，就是给出一系列导弹的高度，问在一个拦截系统的情况下，最多能打下几个导弹，是一道DP题。
这题也可以看作DP，但这次是在给出一系列导弹的情况下，求需要几个拦截系统。
我们可以把由同一个拦截系统负责打下的导弹归为一组。
假设在输入某一系列的导弹高度中，前N个导弹有X组（即需要X个拦截导弹系统），那么第N+1个导弹无非有两种情况：
1.把这个导弹归到X组中的一组，即不增加拦截系统
2.开启新的一组，即增加一个拦截系统
那么什么时候满足1呢？ 就是前X组中有一组的最后一个导弹（即高度最低的导弹）比现在这个第N+1的导弹高度还高。
如 5 2 9 1 最后一个导弹高度为1,那么它可以与5 2同一组，也可以与9同一组
那么什么时候满足2呢？就是前X组中没有一组的最后一个导弹（即高度最低的导弹）比现在这个第N+1的导弹高度还高。
如 5 2 9 10 最后一个导弹的高度为10，因此需要一个新的拦截系统。
这两种情况已经分析完了，考虑一些细节，就是在考虑第一种情况时到底应该将 1 放到哪一组？
其实很简单，如 5 2 9 1 7 如果1与9一组，很明显7将要新的拦截系统。而如果1与5 2一组，那么7就可以与9一组，不需要新的拦截系统。
因为1与9一组时，这组高度最低为1,失去了后面高度为6,5这些高度与9一组的机会。因此归于哪一组时，应计算每一组高度最低的导弹与为归组的导弹的高度差，取高度差最小的一组。
最后就可通过有几组来判定需要几个拦截系统。
#include <iostream>#include <cstring>#include <vector>#include <cstdio>#include <cmath>using namespace std;const int INF = 65523 * 3;typedef struct node{ int height; bool isLast; // 判断是否为这组的最后一位}node;int main(){ vector <node> v; // 记录各导弹的高度 int i, j, N; int temp; // 输入的值 node t; int dis, target; // 与这个高度的差值, 以及这个高度在这数组排第几位 int need; // 需要几套系统 while( cin >> N ) { if( !N ) { printf("0\n"); continue; } v.clear(); // 初始化 need = 0; scanf( "%d", &temp ); t.height = temp; t.isLast = true; need ++; v.push_back(t); // 读入第一个 for( i=1;i<N;i++ ) { scanf( "%d", &temp ); t.height = temp; t.isLast = true; need ++; v.push_back(t); dis = INF; for( j=0;j<i;j++ ) if( v[j].height >= t.height && v[j].isLast ) // 寻找该导弹的前驱 { if( v[j].height-t.height < dis ) // 取差值最小的最为前驱 { dis = v[j].height - t.height; target = j; } } if( dis!=INF ) { v[target].isLast = false; // 取消前驱做为一个导弹拦截系统的最后一个目标导弹 need --; // 因此取消一个导弹拦截系统 } } printf("%d\n", need); } return 0;}
Hdu 1257 最少拦截系统
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。