首页 > 代码库 > 作业题
作业题
作业题
时间限制:3000 ms | 内存限制:65535 KB
难度:3
- 描述
小白同学这学期有一门课程叫做《数值计算方法》,这是一门有效使用数字计算机求数学问题近似解的方法与过程,以及由相关理论构成的学科……
今天他们的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
解题思路:因为横坐标没有重复,所以对横坐标进行排序后,转换成对纵轴求最长(递增或递减)子序列;
# include <stdio.h># include <stdlib.h># include <string.h># define MAX 2000# define max(a,b)a>b?a:btypedef struct Node{ int x,y;}Node;int com(const void *a,const void *b){ struct Node *c = (Node*)a; struct Node *d = (Node*)b; if (c->y != d->y ) return c->x - d->x;}int main(void){ int i,j,m,n,dp1[MAX],dp2[MAX],count; Node a[MAX]; scanf("%d", &m); while (m--) { scanf("%d", &n); memset(dp1,0,MAX*sizeof(int)); memset(dp2,0,MAX*sizeof(int)); for (i = 0; i < n; i++) scanf("%d%d",&a[i].x,&a[i].y); qsort(a,n,sizeof(a[0]),com); for (i = 1; i < n; i++) for (j = i - 1; j >= 0; j--) { if (a[j].y < a[i].y) dp1[i] = max(dp1[i],dp1[j] + 1); if (a[j].y > a[i].y) dp2[i] = max(dp2[i],dp2[j] + 1); } count = 0; for (i = 0; i < n; i++) { count=max(count,dp1[i]); count=max(count,dp2[i]); } printf("%d\n", count + 1); } return 0;}
最优代码
#include<iostream>
02.
#include<cstdio>
03.
#include<cstring>
04.
#include<algorithm>
05.
#include<functional>
06.
using
namespace
std;
07.
#define CLR(arr,val) memset(arr,val,sizeof(arr))
08.
const
int
MAX=10010;
09.
int
y[MAX],tmp[MAX],tmp2[MAX];
10.
int
main()
11.
{
12.
int
t,n,x,top1,top2;
13.
scanf
(
"%d"
,&t);
14.
while
(t--)
15.
{
16.
CLR(y,0);
17.
scanf
(
"%d"
,&n);
18.
for
(
int
i=0;i!=n;i++)
19.
{
20.
scanf
(
"%d"
,&x);
21.
scanf
(
"%d"
,&y[x-1]);
22.
}
23.
top1=top2=0;
24.
int
num=
remove
(y,y+MAX,0)-y;
25.
for
(
int
i=0;i!=num;i++)
26.
{
27.
int
*p=lower_bound(tmp,tmp+top1,y[i]);
28.
int
*q=lower_bound(tmp2,tmp2+top2,y[i],greater<
int
>());
29.
if
(p-tmp==top1) ++top1;
30.
if
(q-tmp2==top2) ++top2;
31.
*p=y[i];
32.
*q=y[i];
33.
}
34.
35.
printf
(
"%d\n"
,max(top1,top2));
36.
}
37.
}
复制去Google翻译翻译结果
#include<iostream>
02.
#include<cstdio>
03.
#include<cstring>
04.
#include<algorithm>
05.
#include<functional>
06.
using
namespace
std;
07.
#define CLR(arr,val) memset(arr,val,sizeof(arr))
08.
const
int
MAX=10010;
09.
int
y[MAX],tmp[MAX],tmp2[MAX];
10.
int
main()
11.
{
12.
int
t,n,x,top1,top2;
13.
scanf
(
"%d"
,&t);
14.
while
(t--)
15.
{
16.
CLR(y,0);
17.
scanf
(
"%d"
,&n);
18.
for
(
int
i=0;i!=n;i++)
19.
{
20.
scanf
(
"%d"
,&x);
21.
scanf
(
"%d"
,&y[x-1]);
22.
}
23.
top1=top2=0;
24.
int
num=
remove
(y,y+MAX,0)-y;
25.
for
(
int
i=0;i!=num;i++)
26.
{
27.
int
*p=lower_bound(tmp,tmp+top1,y[i]);
28.
int
*q=lower_bound(tmp2,tmp2+top2,y[i],greater<
int
>());
29.
if
(p-tmp==top1) ++top1;
30.
if
(q-tmp2==top2) ++top2;
31.
*p=y[i];
32.
*q=y[i];
33.
}
34.
35.
printf
(
"%d\n"
,max(top1,top2));
36.
}
37.
}
作业题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。