希望更丰富的展现？[使用Markdown](https://www.luogu.org/wiki/show?name=%E5%B8%AE%E5%8A%A9%EF%BC%9Amarkdown)
by 「已注销」 @ 2019-04-17 20:58:44
@[Lord_Worms](/space/show?uid=160735)
~~qnd萌新~~
您是不是要问为什么反着求最长上升子序列改成正着求最长下降子序列不行qwq
本菜喵也不是很懂（如果正序求最长上升子序列的时候dp1(j)表示原序列前i个元素的最长上升子序列，那么正序求最长下降子序列dp2(j)表示前i个元素的最长下降子序列
原序列这样的话：
a[1] a[2] a[3] a[4] ... a[i] a[i+1] ... a[n]
那么dp1[i]+dp2[i]就只考虑到了前i项
前i项的最长上升子序列+前i项的最长下降子序列……明显是错的吧
（为啥这样能60分）
我有啥想法错了欢迎回怼qwq
by Kan_kiz @ 2019-04-17 21:28:48
————来自DP渣渣
by Kan_kiz @ 2019-04-17 21:29:32
@[千柒__](/space/show?uid=135926) 对呀，就是不懂为什么还能60...
by Lord_Worms @ 2019-04-18 13:15:27
@[Lord_Worms](/space/show?uid=160735) 数据过水qwq
by Kan_kiz @ 2019-04-18 13:24:14
#include<bits/stdc++.h>
using namespace std;
int n,a[105],dp[2][105],ans;
int main()
{
scanf("%d",&n);
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
a[0]=0;
for(int i=1;i<=n;i++)
for(int j=0;j<i;j++)
if(a[i]>a[j]) dp[0][i]=max(dp[0][i],dp[0][j]+1);
a[n+1]=0;
for(int i=n;i>=1;i--)
for(int j=n+1;j>i;j--)
if(a[i]>a[j]) dp[1][i]=max(dp[1][i],dp[1][j]+1);
for(int i=1;i<=n;i++)
ans=max(dp[0][i]+dp[1][i]-1,ans);
printf("%d\n",n-ans);
return 0;
}
by 过往梦魇之殇 @ 2019-04-20 12:03:07