小白同学这学期有一门课程叫做《数值计算方法》,这是一门有效使用数字计算机求数学问题近似解的方法与过程,以及由相关理论构成的学科……
今天他们的Teacher S,给他们出了一道作业题。Teacher S给了他们很多的点,让他们利用拉格朗日插值公式,计算出某严格单调函数的曲线。现在小白抄下了这些点,但是问题出现了,由于我们的小白同学上课时走了一下神,他多抄下来很多点,也就是说这些点整体连线不一定还是严格递增或递减的了。这可怎么处理呢。为此我们的小白同学制定了以下的取点规则:
1、取出尽可能多的满足构成严格单调曲线的点,作为曲线上的点。
2、通过拉格朗日插值公式,计算出曲线的方程
但是,他又遇到了一个问题,他发现他写下了上百个点。[- -!佩服吧],这就很难处理了(O_O).。由于拉格朗日插值公式的计算量与处理的点数有关,因此他请大家来帮忙,帮他统计一下,曲线上最多有多少点,以此来估计计算量。
已知:没有任何两个点的横坐标是相同的。
2 2 1 2 3 4 3 2 2 1 3 3 4
2 2
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <vector> 6 #include <climits> 7 #include <algorithm> 8 #include <cmath> 9 #define LL long long 10 using namespace std; 11 struct Point{ 12 int x,y; 13 }p[1000]; 14 int dp[1000]; 15 bool cmp(const Point &a,const Point &b){ 16 if(a.x == b.x) return a.y < b.y; 17 return a.x < b.x; 18 } 19 int main(){ 20 int kase,n,i,ans,j; 21 scanf("%d",&kase); 22 while(kase--){ 23 scanf("%d",&n); 24 for(i = 0; i < n; i++) 25 scanf("%d %d",&p[i].x,&p[i].y); 26 memset(dp,0,sizeof(dp)); 27 sort(p,p+n,cmp); 28 ans = 1; 29 for(i = 0; i < n; i++){ 30 dp[i] = 1; 31 for(j = i-1; j >= 0; j--){ 32 if(p[j].y < p[i].y && dp[i] < dp[j]+1) dp[i] = dp[j]+1; 33 } 34 if(dp[i] > ans) ans = dp[i]; 35 } 36 for(i = 0; i < n; i++){ 37 dp[i] = 1; 38 for(j = i-1; j >= 0; j--){ 39 if(p[j].y > p[i].y && dp[i] < dp[j]+1) dp[i] = dp[j]+1; 40 } 41 if(dp[i] > ans) ans = dp[i]; 42 } 43 printf("%d\n",ans); 44 } 45 return 0; 46 }
原文:http://www.cnblogs.com/crackpotisback/p/3833704.html