思路：分別求出單調上升和單調下降的序列長度，然后直接求出答案。

#include <cstdio> #include <iostream> #include <cstring> using namespace std; const int N=105; int n,top,ans,a[N],s[N],f[3][N]; int main() {scanf("%d", &n);for(int i=1; i<=n; i++)scanf("%d", &a[i]);//單調上升 for(int i=1; i<=n; i++){if(a[i] > s[top])//如果可以保持單調性就插入棧 {s[++top] = a[i];f[0][i] = top;}else //否則尋找棧里的數替換 {int L = 1,R = top;while(L < R)//二分求出要替換的數，{int mid = (L + R) / 2;if(s[mid] < a[i]) L = mid + 1;else R = mid;}s[R] = a[i];//R為要替換數的位置 f[0][i] = top;//記錄下棧的長度 }}top = 0;memset(s,0,sizeof(s));//單調下降，操作類似于單調上升 for(int i=n; i>=1; i--){if(a[i] > s[top]){s[++top] = a[i];f[1][i] = top;}else{int L = 1,R = top;while(L < R){int mid = (L + R) / 2;if(s[mid] < a[i]) L = mid+1;else R = mid;}s[R] = a[i];f[1][i] = top;}}for(int i=1; i<=n; i++)ans = max(ans, f[0][i] + f[1][i] - 1);//答案為單調上升加上單調下降再減去多加的一個 printf("%d", n - ans);//減去留在隊列里的數字即為答案 return 0; }

轉載于:https://www.cnblogs.com/N-S-P/p/10802062.html

總結

以上是生活随笔為你收集整理的题解 P1091 【合唱队形】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。