导弹拦截

动态规划

题解

发布日期: 2022-06-13

更新日期: 2023-04-17

文章字数: 1.3k

阅读时长: 6 分

题目链接

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;
}