本文主要是介绍HDU - 1257 —— 最少拦截系统 —— dp+贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.
8 389 207 155 300 299 170 158 65
2
这道题其实刚开始想的复杂了，因为之前做过一道树状数组的题目。我就想用其中的算法，可以求得每一个导弹后面高度大于自己的导弹的数目。
是想出来以后，每次从前面的话会受后面导弹的影响，但是如果从那个后面处理的话，不能够及时对前面的导弹做出更新。所以我放弃了这种做法.
用dp的思路就是开始没有任何一条系统，直到发现当前系统最小的不能够大于新来的导弹高度时就ans ++;就相当于是增加了一条新的控制系统。
贪心体现在每次选择和当前所有的系统中最接近的系统匹配。
注：注释部分是刚开始的错误思路。。
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <stack>
#include <map>
#include <vector>
#include <cmath>
#include <algorithm>using namespace std;#define MAX_N 100005
#define INF 0x3f3f3f3f
#define Mem(a,x) memset(a,x,sizeof(a))
#define ll long longint h[MAX_N],tree[MAX_N],m[MAX_N],dp[MAX_N];
bool vis[MAX_N];
//int lowbit(int x)
//{
// return x&(-x);
//}
//void che(int p,int r)
//{
// for(int i = p; i<=MAX_N; i+=lowbit(i))
// {
// tree[i] += r;
// }
//}
//int sum(int x)
//{
// int con = 0;
// for(int i = x; i>=1; i-=lowbit(i))
// {
// con += tree[i];
// }
// return con;
//}
int main()
{int n;while(~scanf("%d",&n) && n){
// Mem(vis,false);
// Mem(tree,0);//dp[0] = INF;int ans = 0,g;for(int i = 0; i<n; i++){scanf("%d",&g);if(ans == 0) dp[ans] = g;int mint = INF,cur;bool flag = false;for(int j = 0; j<ans; j++) {if(g < dp[j] && mint > dp[j]-g) {mint = dp[j] - g;flag = true;cur = j;}}if(flag) {dp[cur] = g;}else {dp[ans] = g;ans ++;}}printf("%d\n",ans);
// for(int i = n-1; i>=0; i--)
// {
// che(h[i],1);
// int ans = 0;
// ans = n-i-1-sum(h[i]-1);
// m[i] = ans; // 记录每个导弹后面比它自己还要高的导弹的个数
// }cout<<endl;for(int i = 0; i<n; i++) cout<<m[i]<<' ';cout<<endl;
// int getc = 0,ans = 0;
// for(int i = 0; i<n; i++)
// {
// if(vis[i]) continue;
// vis[i] = true;
// int f = 1,cur = 0;
// for(int j = n-1; j>i; j--)
// {
// if(!vis[h[j]] && f)
// {
// vis[h[j]] = true;
// f = 0;
// cur = m[j];
// }
// if(m[j] >= cur && !vis[h[j]]) {
// vis[h[j]] = true;
// cur = m[j];
// }
// }
// ans ++;
// if(f) break;
// }
// cout<<ans<<endl;// while(true) {
// Mem(dp,0);
// for(int i = 0; i<n; i++) {
// dp[i] = 1;
// for(int j = 0; j<i; j++) {
// if(h[i] < h[j]) {
// dp[i] = max(dp[i],dp[j]+1);
// }
// }
// }
// }}return 0;
}
这篇关于HDU - 1257 —— 最少拦截系统 —— dp+贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
