Vijos p1303导弹拦截（LIS+贪心)
来源：程序员人生 发布时间：2014-11-13 08:21:07 阅读次数：3309次
传送门：https://vijos.org/p/1303
背景
实中编程者同盟为了培养技术高深的后备人材，必须从基础题开始训练。
描写
某国为了防御敌国的导弹攻击，研发出1种导弹拦截系统。但是这类导弹拦截系统有1个缺点：虽然它的第1发炮弹能够到达任意的高度，但是以后每发炮弹都不能高于前1发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在实验阶段，所以只有1套系统，因此有可能不能拦截所有的导弹。
格式
输入格式
输入数据只有1行，该行包括若干个数据，之间用半角逗号隔开，表示导弹顺次飞来的高度（导弹最多有 20 枚，其高度为不大于 30000 的正整数）。
输出格式
输出数据只有1行，该行包括两个数据，之间用半角逗号隔开。第1个数据表示这套系统最多能拦截的导弹数；第2个数据表示若要拦截所有导弹最少要再添加多少套这样的系统。
样例1
样例输入1
389,207,155,300,299,170,158,65
样例输出1
6,1
思路：LIS,写成这样也是醉了，姿式不够啊，水题1A。第2问就是贪心了，每次选择已有的最小高度，最大的都不够的时候，就添加系统。
代码：
/*
author：Ac_sorry
problem:导弹拦截
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<climits>
#define INF INT_MAX
using namespace std;
int a[50];
int dp[50];
int main()
{
int cnt=0;
scanf("%d",&a[cnt++]);
while(scanf(",%d",&a[cnt])==1)
{
cnt++;
}
//printf("%d----
",cnt);
memset(dp,0,sizeof dp);
dp[0]=1;
for(int i=1;i<cnt;i++)
{
int maxx=0;
for(int j=0;j<i;j++)
{
if(a[i]<a[j]&&dp[j]>maxx)
maxx=dp[j];
}
dp[i]=maxx+1;
}
vector<int> ans;
for(int i=0;i<cnt;i++)
{
int minn=300000,pos=⑴;
for(int j=0;j<ans.size();j++)
{
if(ans[j]<minn&&ans[j]>=a[i])
{
minn=ans[j];
pos=j;
}
}
if(pos==⑴)
ans.push_back(a[i]);
else
ans[pos]=a[i];
}
int maxx=0;
for(int i=0;i<cnt;i++)
{
maxx=max(dp[i],maxx);
}
printf("%d,%d
",maxx,ans.size()⑴);
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
