导弹拦截


题目链接

P1020 [NOIP1999 普及组] 导弹拦截

解析

​ 这题相信大家应该都做过,只是这题多加了一问。

​ 原题是只求最大拦截数,只需求最长不上升子序列。水水的题目,加上另一问求最少需要的系统数,就变成了普及+了。但还是不难,其实只是再求一个最长不下降子序列。

​ 真正的难度是他的数据量!!!

  那么如何分析呢?

  见样例:

	389 207 155 300 299 170 158 65
T 	[1] [2] [3] [4] [5] [6] [7] [8]

最长不上升子序列:取前面比当前的值大,且长度最长的数;
用F[]来表示到取到第i个数所能得到的最大长度,T[]储存原始数值;
递归式就是:F[i]=max(F[i],F[j]+1);(T[j]>=T[i]&&j<i)

代码实现

for(i=1;i<=n;++i)//第一问 
{
	F[i]=1;//每一个序列最少也能拦截一个导弹
	for(int j=1;j<i;++j)if(T[i]<=T[j])F[i]=max(F[i],F[j]+1);
	ANS1=max(ANS1,F[i]);//用ANS1储存第一问的答案
}

  我们看一下样例的拦截个数:

  F [1] [2] [3] [4] [5] [6] [7] [8]

    1  2 3 2 3 4 5 6

  在3 -> 4 的时候 F[i]的值便小了,而T[3]=155,T[4]=300

  好像和所需的系统个数是一样的咧!

  那么遵循“大胆猜测,从不证明的原则” 我们自己手动推测几个数据,发现“k=最长不下降子序列的长度”这一猜想是正确的!!。

  那问题就简单了!我们只需求出最长不下降子序列就可以了!!

  状态转移方程式 F[i]=max(F[i],F[j]+1);(T[i]i)

  代码实现:

memset(F,0,sizeof(F));//要清除一下F[]
for(i=n;i>=1;--i)  //问题二
{
    F[i]=1;
	for(int j=n;j>i;--j)if(T[i]<T[j])F[i]=max(F[i],F[j]+1);
    ANS2=max(ANS2,F[i]); //ANS2储存第二问答案
}

 那么完整代码如下:

// 这个代码可以得100分,总分200分;
#include<iostream>  
#include<cstring>
#include<cstdio>
#include<cctype>
using namespace std;
int T[100000],F[100000];
int main(void)
{
    //freopen("in.txt","r",stdin); //在本地测试时使用 
    int i=1;
    while(scanf("%d",&T[i])==1)i++;
    int n=i-1,ANS1=0,ANS2=0;
    for(i=1;i<=n;++i)//第一问 ,求最长不上升子序列
    {
        F[i]=1;
        for(int j=1;j<i;++j)if(T[i]<=T[j])F[i]=max(F[i],F[j]+1);
        ANS1=max(ANS1,F[i]);
    }
    memset(F,0,sizeof(F));//清除F[]
    for(i=n;i>=1;--i)//第二问,求最长不下降子序列
    {
        F[i]=1;
        for(int j=n;j>i;--j)if(T[i]<T[j])F[i]=max(F[i],F[j]+1);
        ANS2=max(ANS2,F[i]);
    }
    printf("%d\n%d",ANS1,ANS2);//输出
    return 0;
}

以上是普及组需要的程度!!!接下来讲提高组!!!

这题的数据是加强版的,所以上述方法是不行滴!

那么要怎么办呢???

此处就需要学习一下树状数组这密西!!!推荐博客:  树状数组 数据结构详解与模板(可能是最详细的了)

看完树状数组,我们来讲一下具体实现!!!

先上代码:

//加强版数据 200分
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<iostream>
using namespace std;
long long w[100008],f[100008], maxn=0;
inline long long lowbit(long long x)  //lowbit函数,具体干嘛详见:https://blog.csdn.net/bestsort/article/details/80796531
{
	return x&(-x);
}
inline void Add_Tree(long long x,long long  y) //将当前序列长度插入树状数组中
{
	for(long long i=x; i<=maxn; i+=lowbit(i)) f[i]=max(f[i],y);
}
inline long long Query_Tree(long long x)//查询大于x的最大长度!!!
{
	long long Ans=0;
	for(long long i=x; i>=1; i-=lowbit(i)) Ans=max(Ans,f[i]);
	return Ans;
}
int main(void)
{
	//freopen("in.txt","r",stdin);  // 本地输入时必备
	long long n=1,Ans1=0,Ans2=0;  // n为导弹总个数,ANS1为
	while(scanf("%d",&w[n])!=EOF)
		maxn=max(maxn,w[n]),n++;  // 用maxn存储导弹最大高度
	n--;
	for(long long i=n; i>=1; --i) // 从后往前寻找最长不下降子序列
	{
		long long T=Query_Tree(w[i])+1; // 寻找到第i个导弹最大拦截数
		Add_Tree(w[i],T);// 把当前长度加入树状数组中
		Ans1=max(Ans1,T);// ANS1为第一问答案
	}
	memset(f,0,sizeof(f));
	for(long long i=1; i<=n; ++i)// 从前往后寻找最长下降子序列
	{
		long long T=Query_Tree(w[i]-1)+1;//注意 w[i]-1,因为是在找最长下降子序列
		Add_Tree(w[i],T);
		Ans2=max(Ans2,T);//Ans2为第二问
	}
	printf("%lld\n%lld",Ans1,Ans2);//输出
	return 0;
}

 

  


如果本文帮助到了你,帮我点个广告可以咩(o′┏▽┓`o)


评论
 上一篇
软件推荐-Listary Pro 软件推荐-Listary Pro
Listary Pro是一个高效的Windows搜索工具,其为 Windows 传统低效的文件打开/保存对话框提供了便捷、人性化的文件(夹)定位方式,同时改善了常见文件管理器中文件夹切换的效率。如果你是一个喜欢追求高效率和流畅操作的人,如果你有大量文件需要管理,Listary 是你必备的工具。
2022-06-14
下一篇 
乘法逆元 乘法逆元
简单理解:逆元就是在求余意义下的倒数
2022-06-13
  目录