nyoj 814 又見導彈攔截

又見攔截導彈

描述

大家對攔截導彈那個題目應該比較熟悉了，我再敘述一下題意：某國為了防御敵國的導彈襲擊，新研制出來一種導彈攔截系統。但是這種導彈攔截系統有一個缺陷：它的第一發炮彈能夠到達任意的高度，但是以後每一發炮彈都不能超過前一發的高度。突然有一天，雷達捕捉到敵國的導彈來襲。由於該系統存在缺陷，所以如果想把所有的導彈都攔截下來，就要多准備幾套這樣的導彈攔截系統。但是由於該系統成本太高，所以為了降低成本，請你計算一下最少需要多少套攔截系統。

輸入

有多組測試數據。
每組數據先輸入一個整數N（N≤3000），代表有N發導彈來襲。接下來有N個數，分別代表依次飛來的導彈的導彈的高度。當N=-1時表示輸入結束。

輸出

每組輸出數據占一行，表示最少需要多少套攔截系統。

方法一：時間為1084ms

#include
#include
#include
int dp[3005];
int data[3005];
int main()
{
    int n;
    while(scanf("%d",&n)&&n!=-1)
    {
     int i,j;
     for(i=0;i

方法二：時間為40ms

#include
int main()
{
	int n,i,j,c,a[3000],dp[3000];
	while(1)
	{
		scanf("%d",&n);
		if(n==-1)break;
		for(i=0;i=c)
			{dp[j]=a[i];c++;}
		}
		printf("%d\n",c);
	}
	return 0;
} 


方法三：

與方法二類似
只是采用了二分的思想來查找第一個比他大的
時間為36ms
#include
#define MAX 3005

//二分查找，大於key的最小f[]的位置j
int UpBinarySearch(int *upF,int l, int r, int key)
{
	if (l<=r)
	{
		int mid = (l + r) / 2;

		if (upF[mid] >= key)
		{
			return UpBinarySearch(upF,l, mid-1, key);
		}
		else
		{
			return UpBinarySearch(upF, mid+1, r, key);
		}
	}
	else
	{
		return l;
	}
}

int main()
{
	int a[MAX];
	int f[MAX];
	int aUp[MAX];
    int k = 0;//length
	int i = 0, n=0;//loop

	//讀入
	while(scanf("%d",&n)&&n!=-1)
	{
                        
	for (i=1; i<=n; i++)
	{
		scanf("%d",&a[i]);
	}
	//正著上升求序
	f[0] = -9999;
	k = 0;
	for (i=1; i<=n; i++)
	{
		if (f[k]