分析题目知道求一个最长上升子序列和一个最长下降子序列的长度均为同一个起点的最长的长度。于是求
点击查看代码
#include <iostream>
#include <stack>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>
#include <climits>
#include <string.h>
#include <map>
#include <queue>
#include <list>
#include <cmath>
#include <iomanip>
#define int long long
#define ios ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lc u<<1
#define rc u<<1|1
#define gcd __gcd
#define double long double
#define endl "\n"
#define INF LLONG_MAX
#define mod 998244353
#define N 105
const double PI = 3.14159265358979323846;
using namespace std;
int n, t[N], a[N], b[N];//分别表示以该数结尾最长子序列的长度
signed main()
{
ios;
int n; cin >> n;
for (int i = 1; i <= n; i++)cin >> t[i];
for (int i = 1; i <= n; i++)
{
a[i] = 1;
for (int j = 1; j < i; j++)
{
if (t[i] > t[j])a[i] = max(a[i], a[j] + 1);
else continue;
}
}
for (int i = n; i >=1; i--)
{
b[i] = 1;
for (int j = n; j > i; j--)
{
if (t[i] > t[j])b[i] = max(b[i], b[j] + 1);
else continue;
}
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
//cout << a[i] << " " << b[i] << endl;
ans = max(a[i] + b[i] - 1, ans);
}
cout << n - ans << endl;
return 0;
}