NYOJ 201 作業題

作業題

描述

小白同學這學期有一門課程叫做《數值計算方法》，這是一門有效使用數字計算機求數學問題近似解的方法與過程，以及由相關理論構成的學科……

今天他們的Teacher S，給他們出了一道作業題。Teacher S給了他們很多的點，讓他們利用拉格朗日插值公式，計算出某嚴格單調函數的曲線。現在小白抄下了這些點，但是問題出現了，由於我們的小白同學上課時走了一下神，他多抄下來很多點，也就是說這些點整體連線不一定還是嚴格遞增或遞減的了。這可怎麼處理呢。為此我們的小白同學制定了以下的取點規則：

1、取出盡可能多的滿足構成嚴格單調曲線的點，作為曲線上的點。

2、通過拉格朗日插值公式，計算出曲線的方程

但是，他又遇到了一個問題，他發現他寫下了上百個點。[- -!佩服吧],這就很難處理了(O_O).。由於拉格朗日插值公式的計算量與處理的點數有關，因此他請大家來幫忙，幫他統計一下，曲線上最多有多少點，以此來估計計算量。

已知：沒有任何兩個點的橫坐標是相同的。

輸入

本題包含多組數據：
首先，是一個整數T，代表數據的組數。
然後，下面是T組測試數據。對於每組數據包含兩行：
第一行：一個數字N(1<=N<=999),代表輸入的點的個數。
第二行：包含N個數對X(1<=x<=10000),Y(1<=Y<=10000),代表所取的點的橫縱坐標。

輸出

每組輸出各占一行，輸出公一個整數，表示曲線上最多的點數

樣例輸入

2
2
1 2 3 4
3
2 2 1 3 3 4

樣例輸出

2
2

AC碼：

#include
#include
struct node
{
	int x;
	int y;
}num[1003];
int cmp(const void *a,const void *b)
{
	return (((struct node *)a)->x-((struct node *)b)->x);
}
int main()
{
	int T,n,count[1003],c2[1003],i,j;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(i=0;i=0;i--)
		{
			for(j=i+1;j(count[j]+1)?count[i]:(count[j]+1));
					if(count[i]>max)
						max=count[i];
				}
				else
				{
					c2[i]=(c2[i]>(c2[j]+1)?c2[i]:(c2[j]+1));
					if(c2[i]>max)
						max=c2[i];
				}
			}
		}
		printf("%d\n",max);
	}
	return 0;
}