导弹拦截问题 C程序 动态规划

来源：百度知道 编辑：UC知道 时间：2024/06/14 14:31:53
问题描述：某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
编程任务：输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000 的正整数），计算这套系统最多能拦截多少导弹，并依次输出被拦截的导弹飞来时候的高度。
得分系数：时间复杂度O(n*n) 75，时间复杂度O(n*logn) 85

我给你写了一个，不过得出的序列可能并不是唯一的，但保证是正确的！时间复杂度是O(n^2)，你所说的n*logn的目前我是做不出来，等做出来再告诉你吧！
#include<iostream>

using namespace std;

int main()
{
int i,j,n,x[100],d[100]; //x[]表示各个导弹高度，d[i]记录为第 i 枚导弹被拦截之后，
//这套系统最多还能拦截的导弹数（包含被拦截的第 i 枚）。
int dmax=0,xh=0; //记录拦截的最大个数以及第一个被拦截的序号
cin>>n; //输入拦截的导弹数
for(i=0;i<n;i++)
{
cin>>x[i]; //输入每个导弹的高度
d[i]=1; //初始值都设为1
}
for(i=n-2;i>=0;i--) //动态规划算法，递归实现,从后面向前循环
{
for(j=i+1;j<n;j++)
if((x[j]<x[i])&&(d[i]<d[j]+1)) //判断条件
{
d[i]=d[j]+1;
}
}
for(i=0;i<n;i++) //找出最大个数
{
if(d[i]>dmax)
{
dmax=d[i];
xh=i; //第一枚被拦截的导弹序号
}
}
cout<<d[xh]<<endl;
cout<<x[xh]<<",";
for(j=xh+1;j<n;j++) //依次输出满足条件的递减序号
if((x[j]<=x[xh])&&(d[xh]==d[j]+1)) //判断条件
{
cout