登山(动态规划)
作者:
amagi
,
2023-06-04 21:49:12
,
所有人可见
,
阅读 147
#include <iostream>
#include <cstring>
#include <map>
using namespace std;
const int N = 1001;
int x[N],y[N],z[N];
// map<int,int>Map;
int main(){
int a;
cin >> a;
for(int i = 1; i <= a; i ++) cin >> x[i];
for(int i = 0; i <= a + 10; i ++) y[i] = z[i] = 1;
for(int i = 1; i <= a; i ++){
for(int j = 1; j < i; j ++){
if(x[j] < x[i]){
y[i] = max(y[i],y[j] + 1);
}
}
}
for(int i = a; i >= 1; i --){
for(int k = a; k > i; k --){
if(x[k] < x[i]) z[i] = max(z[i],z[k] + 1);
}
}
int res = -2;
for(int i = 1; i <= a; i ++) res = max(res,y[i] + z[i] - 1);
cout << res << endl;
}