pat顶级1017 The Best Peak Shape （35 point(s)）

本文主要是介绍pat顶级1017 The Best Peak Shape （35 point(s)），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

欢迎访问我的pat顶级题解目录哦 https://blog.csdn.net/richenyunqi/article/details/86751676

题目描述

pat顶级1017 The Best Peak Shape （35 point(s)）题目描述

算法设计

这是一道考察最长上升子序列问题（LIS）的题目。定义数组A[n+1]存储整个序列；定义数组dpLeft[n+1]，其中dpLeft[i]表示序列A[1]~A[i]中以A[i]结尾的不包含A[i]的最长上升子序列的长度；定义数组dpRight[n+1]，其中dpRight[i]表示序列A[n]~A[i]中以A[i]结尾的不包含A[i]的最长上升子序列的长度。
那么对于A[i]，存在以A[i]为中心的peak shape的条件为dpleft[i]>0&&dpRight[i]>0，整个peak shape的长度为dpleft[ans]+dpRight[ans]+1。
关于dpLeft和dpRight的求解大致相同，以dpLeft为例，其状态转移方程为 $dpLeft[i]=max\{dpLeft[i],dpLeft[j]+1|j<i,A[j]<A[i]\}$
具体实现可见代码。

C++代码

#include<bits/stdc++.h>
using namespace std;
int main(){int n,ans=0;//ans存储最终结果peak number的下标scanf("%d",&n);int A[n+1],dpleft[n+1]={0},dpRight[n+1]={0};//将dpleft、dpRight均初始化为0for(int i=1;i<=n;++i)scanf("%d",&A[i]);for(int i=1;i<=n;++i)//求解dpLeftfor(int j=1;j<i;++j)if(A[i]>A[j])dpleft[i]=max(dpleft[i],dpleft[j]+1);for(int i=n;i>=1;--i)//求解dpRightfor(int j=n;j>i;--j)if(A[i]>A[j])dpRight[i]=max(dpRight[i],dpRight[j]+1);for(int i=1;i<=n;++i)//求解ansif(dpleft[i]>0&&dpRight[i]>0&&(dpleft[i]+dpRight[i]>dpleft[ans]+dpRight[ans]||(dpleft[i]+dpRight[i]==dpleft[ans]+dpRight[ans]&&abs(dpleft[i]-dpRight[i])<abs(dpleft[ans]-dpRight[ans]))))ans=i;if(ans==0)puts("No peak shape");elseprintf("%d %d %d",dpleft[ans]+dpRight[ans]+1,ans,A[ans]);return 0;
}