思路
特征 求一个最长的序列，中间值前面上升，后面下降
// 然后就可以拆分成以中间值为结尾的最长上升子序列和以中间值为开头的最长下降子序列，分别求后再加在一起即可。
需要注意的是，求得的和需要减一，因为中间值被重复加了两次，长度多了1
题解妙在将题目数组的状态以特殊点为边界，拆解成了两个dp子问题。
套路
以i结尾的最长连续上升子序列
for(int i = 1;i <= n;i++){ f[i] = 1; for(int j = 1;j < i;j++){ if(a[i] > a[j]) f[i] = max(f[i],f[j]+1); } }
以i开头的最长连续上升子序列
for(int i = n;i;i--){ f[i] = 1; for(int j = n;j > i;j--){ if(a[i] < a[j]) f[i] = max(f[i],f[j]+1); } }
以i结尾的最长连续下降子序列
for(int i = 1;i <= n;i++){ f[i] = 1; for(int j = 1;j <= n;j++){ if(a[i] < a[j]) f[i] = max(f[i],f[j]+1); } }
以i开头的最长连续下降子序列
for(int i = n;i;i--){ f[i] = 1; for(int j = n;j > i;j--){ if(f[i] > f[j]) f[i] = max(f[i],f[j]+1); } }
注意到以i结尾时，写法变为从1到n
for(int i = 1;i <= n;i++) 和 for(int j = 1;j < i;j++)
以i开头时，写法则变为从n到1
for(int i = n;i;i--) 和 for(int j = n;j > i;j--);
求以i结尾最长上升子序列时，写法变为
if(a[i] > a[j])
求以i开头最长上升子序列时，写法变为
if(a[i] < a[j])
求以i结尾最长下降子序列时，写法变为
if(a[i] < a[j])
求以i开头最长下降子序列时，写法变为
if(a[i] > a[j])
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; const int N = 110; int f[N],cnt[N],a[N]; int main(){ int n; cin >> n; for(int i = 1;i <= n;i++) cin >> a[i]; for(int i = 1;i <= n;i++){ f[i] = 1; for(int j = 1;j < i;j++) if(a[j] < a[i]) f[i] = max(f[j]+1,f[i]); cnt[i] += f[i]; } for(int i = n;i;i--){ f[i] = 1; for(int j = n;j > i;j--) if(a[j] < a[i]) f[i] = max(f[j] + 1,f[i]); cnt[i] += f[i] -1 ; // cout << cnt[i] << " " ; } int res = 0x3f3f3f3f; for(int i= 1;i <= n;i++){ // cout << cnt[i] << " " ; res = min(n-cnt[i],res); } cout << res << endl; return 0; }
