Question

杭电1257 求错在哪里！！

Problem Description
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.

Input
输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)

Output
对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.

Sample Input
8 389 207 155 300 299 170 158 65

Sample Output
2

我的代码，我是求子序列的个数。如果后面的数字如果比前面的所有子序列的最后一个都大，就必须要增加一个子序列
#include<iostream>
using namespace std;
int main()
{
int n,a[30001];//a为子序列数组
while((cin>>n)&&(n))
{
int *p=new int[n];
for(int i=0;i<n;i++)
cin>>p[i];
int count=0,k=1;//count为所求子序列个数
a[0]=p[0];
for(int i=0;i<n-1;i++)
{
if(p[i]<p[i+1])
{
a[count]=p[i];
for(int j=0;j<=count;j++)
{
if(p[i+1]<a[j])
{
a[j]=p[i];
k=0;
break;
}
}
if(k)
count++;
}
}
cout<<count+1<<endl;
delete []p;
}
return 0;
}

Answer 1

思路是对的，但是代码写的好像不对。
1）k作为标记，每次循环前都要赋初值1
2）if(p[i]<p[i+1]) 这里可能你是想取出一段连续的非升序列的最后的元素即最小值。但是在可能该最小值可以包含在之前计算的子序列中，但是非升序列中最小值之前的元素不能被包含在与最小值相同的子序列中。

我在你写的代码上做了修改，你写的有些的地方我看不太懂，所以可能也没完全按你原来的想法去改错。
#include<iostream>
using namespace std;
int main()
{
int n,a[30001];//a为子序列数组
while((cin>>n)&&(n))
{
int i, j;
int *p = new int[n];
for(i = 0; i < n; i ++)
cin >> p[i];
int count = 0, k;//count为所求子序列个数
a[0] = p[0];
for(i=0;i<n-1;i++)
{
k = 1; // k作为标记，每次循环前都要赋初值啊
for(j=0;j<=count;j++)
{
if(p[i+1]<=a[j])
{
a[j]=p[i + 1];
k=0;
break;
}
}
if(k)
{
count++;
a[count] = p[i + 1];
}
}
cout<<count+1<<endl;
delete []p;
}
return 0;
}