好家伙,这山最高5000米,我写一万米给我MLE了
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int f[N][N*5];//i表示前i个点,j表示最大值,f表示选点数
int m[N][N*5];//后i个数中最大海拔为j的情况里面能选多少个数(最长下降子序列)
int num[N];
int n;
int main()
{
cin >> n;
int mini = 1e5, maxi = 0;//最大高度,最小高度
for(int i = 1; i <= n; i ++)
{
cin >> num[i];
mini = min(mini, num[i]);
maxi = max(maxi, num[i]);
}
for(int i = 1; i <= n; i ++)
for(int j = mini; j <= maxi; j ++)
{
if(num[i] == j)
{
for(int k = 1; k < j; k ++)
f[i][j] = max(f[i][j], f[i-1][k]);
f[i][j] ++;
}
else f[i][j] = f[i-1][j];
}//登山路线
for(int i = n; i; i --)
for(int j = mini; j <= maxi; j ++)
{
if(num[i] == j)
{
for(int k = 1; k < j; k ++)
m[i][j] = max(m[i][j], m[i+1][k]);
m[i][j] ++;
}
else m[i][j] = m[i+1][j];
}//下山路线
int res = 0;
for(int i = 1; i <= n; i ++)
for(int j = mini; j <= maxi; j ++)
res = max(res, f[i][j]+m[i][j]-1);
cout << res << endl;
// cout << mini << ' ' << maxi << endl;
return 0;
}
其实你把第二维度去掉变成一维dp就不会MLE了