首页 > 代码库 > hdu----(1257)最少拦截系统（dp/LIS）
hdu----(1257)最少拦截系统（dp/LIS）
最少拦截系统
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 19172 Accepted Submission(s): 7600
Problem Description
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.
Input
输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)
Output
对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.
Sample Input
8 389 207 155 300 299 170 158 65
Sample Output
2
Source
浙江工业大学第四届大学生程序设计竞赛
这道题，简单，做法多样，适合用来训练多种dp结构：
比如LIS
代码：
1 //#define LOCAL 2 #include<cstring> 3 #include<cstdio> 4 #include<vector> 5 #include<iostream> 6 using namespace std; 7 const int inf=0x3f3f3f3f; 8 int n; 9 vector<int>aa,ans;10 int binary(int v,int len)11 {12 int r=len,l=1,mid;13 while(l<=r)14 {15 mid=l+(r-l)/2;16 if(ans[mid]<=v)17 l=mid+1;18 else19 r=mid-1;20 }21 return l;22 }23 24 int LIS()25 {26 int i,res=1,j;27 for(i=1;i<=n;i++)28 ans[i]=inf;29 for(i=1;i<=n;i++)30 {31 j=binary(aa[i],res);32 if(res<j) res=j;33 if(ans[j]>=aa[i])34 ans[j]=aa[i];35 }36 return res;37 }38 int main()39 {40 #ifdef LOCAL41 freopen("test.in","r",stdin);42 #endif43 while(scanf("%d",&n)!=EOF)44 {45 aa.resize(n+2);46 ans.resize(n+2);47 for(int i=1;i<=n;i++)48 cin>>aa[i];49 printf("%d\n",LIS());50 }51 return 0;52 }
hdu----(1257)最少拦截系统（dp/LIS）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。