合唱队行 (最长上升子序列)

简介: 合唱队行 (最长上升子序列)

482. 合唱队形 - AcWing题库

列举每一个小朋友当最高点,分左边和右边进行求最长上升子序列,取他们的最大值,最后减去用n减去最长上升子序列就行了

#include<iostream>
#include<cstring>
#include<algorithm>
 
using namespace std ;
const int N = 500;
int f[N] ;
int a[N] ;
int b[N] ;
int main(){
  int n ;
  cin >> n ;
  for(int i = 1 ; i <= n ;i ++) cin >> a[i] ;
  for(int i = 1 ; i <= n ;i ++){
    for(int j = 1 ; j <= i ; j ++) b[j] = a[j] ;
    int len = 0 ;int dp[N] ;
    memset(dp,0,sizeof(dp)) ;
    for(int k = 1 ; k <= i ; k ++){
      dp[k] ++ ;
      for(int l = 1 ; l < k ;l ++ ){
        if(b[k] > b[l]) dp[k] = max(dp[k],dp[l]+1) ;
      }
    }
    len += dp[i] ;
    memset(dp,0,sizeof(dp)) ;
    int cnt = 1 ;
    for(int j = n ; j >= i ; j--) b[cnt++] = a[j] ; 
    cnt -- ;
    for(int k = 1 ; k <= cnt ; k ++){
      dp[k] ++ ;
      for(int l = 1 ; l < k ;l ++ ){
        if(b[k] > b[l]) dp[k] = max(dp[k],dp[l]+1) ;
      }
    }
    len += dp[cnt] ; len -- ;
    f[i] = len ;
  }
  int ans = 0 ;
  for(int i = 1 ; i <= n ; i++) ans = max(ans,f[i]) ;
  cout << n-ans << endl ;
}
目录
相关文章
|
7月前
|
机器学习/深度学习 算法 测试技术
【动态规划】【最长子序列】2901. 最长相邻不相等子序列 II
【动态规划】【最长子序列】2901. 最长相邻不相等子序列 II
【动态规划刷题 15】最长定差子序列&& 最长的斐波那契子序列的长度
【动态规划刷题 15】最长定差子序列&& 最长的斐波那契子序列的长度
【动态规划刷题 13】最长递增子序列&& 摆动序列
【动态规划刷题 13】最长递增子序列&& 摆动序列
|
2月前
acwing 895 最长上升子序列1
acwing 895 最长上升子序列1
30 3
|
2月前
acwing 896 最长上升子序列II
acwing 896 最长上升子序列II
27 2
|
6月前
|
存储
[TJOI2013]最长上升子序列 [SCOI2009]游戏
[TJOI2013]最长上升子序列 [SCOI2009]游戏
20 1
|
7月前
|
算法
LeetCode题:581. 最短无序连续子数组,242. 有效的字母异位词,202. 快乐数
LeetCode题:581. 最短无序连续子数组,242. 有效的字母异位词,202. 快乐数
54 0
|
7月前
|
人工智能 算法 Java
最长连续不重复子序列(蓝桥杯每日一题)
最长连续不重复子序列(蓝桥杯每日一题)
42 0
|
算法
Leecode 300. 最长上升子序列
Leecode 300. 最长上升子序列
68 0
(区间dp最长上升子序列,最长下降子序列)
(区间dp最长上升子序列,最长下降子序列)
111 0