算法
(线性DP,最长上升子序列) $O(n^2)$
假设最优解的中心是第 $i$ 个人，则 $T_1, T_2, …, T_i$ 一定是以 $T_i$ 结尾的最长上升子序列。
同理，$T_K, T_{K-1}, …, T_i$ 也一定是以 $T_i$ 结尾的最长上升子序列。
因此可以先预处理出：
- 从前往后以每个点结尾的最长上升子序列长度
f[i]； - 从后往前以每个点结尾的最长上升子序列长度
g[i]；
那么以 $k$ 为中心的最大长度就是 f[k] + g[k] - 1，遍历 k = 1, 2, ..., n 取最大值即为答案。
求最长上升子序列问题(LIS)可以参考 AcWing 895. 最长上升子序列。
时间复杂度
本题数据范围只有 100，因此可以用朴素的LIS求解方式，时间复杂度是 $O(n^2)$，使用贪心 + 二分可以将时间复杂度优化到 $O(nlogn)$，具体可以参考 AcWing 896. 最长上升子序列 II。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int h[N];
int f[N], g[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
for (int i = 1; i <= n; i ++ )
{
f[i] = 1;
for (int j = 1; j < i; j ++ )
if (h[j] < h[i])
f[i] = max(f[i], f[j] + 1);
}
for (int i = n; i; i -- )
{
g[i] = 1;
for (int j = n; j > i; j -- )
if (h[j] < h[i])
g[i] = max(g[i], g[j] + 1);
}
int res = 0;
for (int i = 1; i <= n; i ++ ) res = max(res, f[i] + g[i] - 1);
printf("%d\n", n - res);
return 0;
}
yz,从后往前求最长上升子序列模型，这样写为什么不对呢，过不掉所有数据
for(int i=1; i<=n; i)
{
g[i] = 1;
for(int j=1; j<=i; j)
if(w[i] < w[j])
g[i] = max(g[i],g[j]+1);
}
明白了，这样求的是从前到自己的递减序列，而不是从自己到末尾的递减序列
是的
我刚才也干了这种事
https://www.acwing.com/activity/content/code/content/7341822/
原来脑抽不止我
复习二刷的时候，发现自己又犯下了错误。。。
为什么我这样不行？有没有大佬指点一下
#蓝桥杯_Acwing_合唱队形(线性DP_最长上升子序列)
n=int(input())
N=110
lst=[0]+list(map(int,input().split()))
dp1,dp2=[0]N,[0]N
for i in range(1,n+1):
dp1[i],dp2[i]=1,1
x=n-i+1
for j in range(1,i):
y=n-j+1
if lst[j]<lst[i]:
dp1[i]=max(dp1[i],dp1[j]+1)
if lst[y]<lst[x]:
dp2[x]=max(dp2[x],dp2[y]+1)
res=0
for i in range(1,n+1):
res=max(res,dp1[i]+dp2[i]-1)
print(n-res)
找到原因了，初始化的时候dp2[x]=1应该写在x=n-i-1后面，
不错啊
谢谢hh
666
跟我想法一毛一样
建议更改题目描述，我就读题懵逼了，”排成“我以为是可以重新排序呢。
....使得剩下的K位同学保持相对顺序不变，形成合唱队形。
牛逼