题目分析
没有看题解,步子也是一点一点摸索出来的
状态表示
f[i]:从0~i的最长上升子序列
w[i]:从0~i的最长下降子序列
重点来了,由题意知,我们的队员是先上山再下山的,所以下山时的最高海拔是低于上山时的最高海拔
而上山阶段也就是一个上升子序列,下山阶段也就是一个下降子序列,所以:
v[i][j]:0~i为上山阶段,j~n+1为下降阶段
那么这里为什么边界要取0和n+1呢?因为我们i=0时可以认为是一直下山的,同理当j=n+1时是一直上山的
状态转移方程
f[i]=max(f[1],f[2],…,f[i])
w[i]=max(w[1],w[2],…,w[i])
#include<iostream>
using namespace std;
const int N=1010;
int a[N],f[N],w[N];
int v[N][N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
f[i]=w[i]=1;//初始为1
}
//计算1~n的最大上升子序列
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
if(a[i]>a[j]) f[i]=max(f[i],f[j]+1);
//计算n~1的最长下降子序列
for(int i=n;i>=1;i--)
for(int j=n;j>=i;j--)
if(a[i]>a[j]) w[i]=max(w[i],w[j]+1);
// 计算参观景点的最大值
int mx=0;//mx是参观景点的最大值
for(int i=0;i<=n;i++)
for(int j=i+1;j<=n+1;j++)
if(a[i]<a[j]) mx=max(mx,f[i]+w[j]);
cout<<mx<<endl;
return 0;
}
相邻的同海拔高度的景点不能连续参观,这个限制条件不用考虑
因为无论是上升子序列还是下降子序列,包括下山时的点,注定海拔不会和前一个相等