1 条题解
-
0
合唱队形
是两边底中间高的序列。设 为 中以 为结尾LIS的长度, 为 中以 为结尾LIS的长度,答案为 。#include<bits/stdc++.h> using namespace std; const int N=105,INF=0x3f3f3f3f; int n,a[N],f[2][N],ans=-INF; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) // 正着求一遍LIS for(int j=0;j<i;j++) // j要从0开始枚举,否则f[1]就会为0而不是1 if(a[j]<a[i]) f[0][i]=max(f[0][i],f[0][j]+1); for(int i=n;i>=1;i--) // 反着求一遍LIS for(int j=n+1;j>i;j--) // j要从n+1开始枚举,否则f[n]就会为0而不是1 if(a[j]<a[i]) f[1][i]=max(f[1][i],f[1][j]+1); for(int i=1;i<=n;i++) // 枚举i点 ans=max(ans,f[0][i]+f[1][i]-1); printf("%d",n-ans); return 0; }
- 1
信息
- ID
- 799
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 4
- 标签
- 递交数
- 107
- 已通过
- 51
- 上传者