PAT (Top Level) Practice 1017 The Best Peak Shape (35 分) 题解
---- >我的GIS/CS学习笔记:https://github.com/yunwei37/ZJU-CS-GIS-ClassNotes <一个浙江大学本科生的计算机、地理信息科学知识库 > 还有不少数据结构和算法相关的笔记以及pta题解哦x ----
PTA top level 练习里面的一道题目...挺简单的,就是读懂题目然后注意一下边界条件。
是浙江大学高级数据结构与算法课程的一个小作业啦
# 思路
就是两个最大上升子序列,从正反两个方向进行,然后把结果叠加到一起就好啦。不算注释的话30行代码...可以说非常少了x
In many research areas, one important target of analyzing data is to find the best "peak shape" out of a huge amount of raw data full of noises. A "peak shape" of length L is an ordered sequence of L numbers { D1, ⋯, DL } satisfying that there exists an index i (1<i<L) such that D1<⋯<Di−1<Di>Di+1>⋯>DL.
Now given N input numbers ordered by their indices, you may remove some of them to keep the rest of the numbers in a peak shape. The best peak shape is the longest sub-sequence that forms a peak shape. If there is a tie, then the most symmetric (meaning that the difference of the lengths of the increasing and the decreasing sub-sequences is minimized) one will be chosen.
Input Specification:
Each input file contains one test case. For each case, the first line gives an integer N (3≤N≤104). Then N integers are given in the next line, separated by spaces. All the integers are in [−10000,10000].
Output Specification:
For each case, print in a line the length of the best peak shape, the index (starts from 1) and the value of the peak number. If the solution does not exist, simply print "No peak shape" in a line. The judge's input guarantees the uniqueness of the output.
Sample Input1:
20
1 3 0 8 5 -2 29 20 20 4 10 4 7 25 18 6 17 16 2 -1
Sample Output1:
10 14 25
Sample Input2:
5
-1 3 8 10 20
Sample Output2:
No peak shape
代码:
/*
Name: The Best Peak Shape
Author: zheng yusheng
Date: 21/04/19 14:27
Description: the solve of project "The Best Peak Shape" using dp algorithm
*/
#include <stdio.h>
#include <math.h>
#define max(a,b) (a>b?(a):(b))
/*forward dp, find the length of the increasing sequence end with the ith number*/
int up[10010];
/*backward dp, find the length of the decreasing sequence end with the ith number*/
int down[10010];
//the number sequence is stored here, begin at num[1];
int num[10010];
int main() {
int n,max,j;
scanf("%d",&n);//get the integer N
int i;
for(i=0; i<n; ++i)
scanf("%d",num+i+1);//get N numbers;
//forward dp: up[i] = the max length of the increasing sequence end with the number before num[i] and smaller than num[i]
for(int i=1; i<=n; i++)
for(int j=1; j<=i-1; j++)
if (num[j] < num[i]) up[i] = max(up[i], up[j] + 1);
//backward dp: up[i] = the max length of the decreasing sequence end with the number after num[i] and smaller than num[i]
for(int i=n; i>=1; i--)
for(int j=n; j>=i+1; j--)
if (num[j] < num[i]) down[i] = max(down[i], down[j] + 1);
//add the results of the forward dp and backward together, and find the max one;
max=0;//the peak position of the max length peak shape(guard:the length is zero)
for(i=1; i<=n; ++i) {
if(up[i]==0||down[i]==0) continue;//skip results that cannot form a peak shape;
else if(up[i]+down[i]>up[max]+down[max])//if the lenth is larger, update the position of the num;
max=i;
else if(up[i]+down[i]==up[max]+down[max]&&abs(up[i]-down[i])<abs(up[max]-down[max]))
max=i;//minimize the difference of the lengths of the increasing and the decreasing sub-sequences
}
if (up[max]+down[max] > 0)//if there exist a solution, output the result
printf("%d %d %d",up[max]+down[max]+1,max,num[max]);
else printf("No peak shape\n");//no solution
return 0;
}
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的