防卫导弹(动态规划入门题）
一种新型的防卫导弹可截击多个攻击导弹.它可以向前飞行,也可以用很快的速度向下飞行,可以毫无损伤地截击进攻导弹,但不可以向后或向上飞行.但有一个缺点,尽管它发射时可以达到任意高度,但它只能截击比它上次截击导弹时所处高度低或者高度相同的导弹.现对这种新型 防卫导弹进行测试,在每一次测试中,发射一系列的测试导弹(这些导弹发射的间隔时间固定,飞行速度相同),该防卫导弹所能获得的信息包括各进攻导弹的高度,以及它们发射次序.现要求编一程序,求在每次测试中,该防卫导弹最多能截击的进攻导弹数量,一个导弹能被截击应满足下列两个条件之一:
它是该次测试中第一个被防卫导弹截击的导弹;
它是在上一次被截击导弹的发射后发射,且高度不大于上一次被截击导弹的高度的导弹.
输入格式:
从当前目录下的文本文件"CATCHER.DAT"读入数据.该文件的第一行是一个整数N(0〈=N〈=4000),表示本次测试中,发射的进攻导弹数,以下N行每行各有一个整数hi(0〈=hi〈=32767),表示第i个进攻导弹的高度.文件中各行的行首,行末无多余空格,输入文件中给出的导弹是按发射顺序排列的.
输出格式:
答案输出到当前目录下的文本文件"CATCHER.OUT"中,该文件第一行是一个整数max,表示最多能截击的进攻导弹数,以下的max行每行各有一个整数,表示各个被截击的进攻导弹的编号(按被截击的先后顺序排列).输出的答案可能不唯一,只要输出其中任一解即可.
题目讲得很麻烦,归根结底就是求一整串数中的最长不上升序列 ，用一个一维数组Max[ i ]来建立动态规划状态转移方程,表示表示当前状态（从i 到n）最多可击落的导弹数，用next[i]表示当前节点的后继标志：
#include<iostream>
#include<string>
using namespace std;
int h[4001],Max[4001],next[4001];
int main()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
int n,head,i,j,maxnum;
while(cin>>n)
{
for(i=1;i<=n;i++)
cin>>h[i];
maxnum=0;
for(i=n;i>=1;i--)
{
Max[i]=1;
next[i]=0;
for(j=i+1;j<=n;j++)
if(h[i]>=h[j])
if(Max[i]<Max[j]+1)
{
Max[i]=Max[j]+1;
next[i]=j;
}
if(Max[i]>maxnum)
{
maxnum=Max[i];
head=i;
}
}
cout<<maxnum<<endl;
while(head!=0)
{
cout<<head<<endl;
head=next[head];
}
cout<<endl;
}
return 0;
}
