題目大意：

給定序列列 a[]，最少修改多少個位置可以令其變成最長上升子序列

分析：

這道題看似非常奇怪，然而細想一下很容易發現我們可以通過令 a’[i] = a[i] - i

對 a’[i] 求最長上升子序列，可以得到最多有多少個位置保持不不變

然后用n去減它，就是要修改的個數

代碼如下：

#include<cstdio> #include<iostream> #include<algorithm> using namespace std;int n,top=1,h[1000101],a[1000101];void add(int x) {int l=1,r=top,m;while(l<=r){m=(l+r)>>1;if(x>=h[m]) l=m+1;else r=m-1;}h[l]=x; }int main() {scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%d",&a[i]);a[i]-=i;}for(int i=1;i<=n;++i){if(a[i]>=h[top]&&i!=1) h[++top]=a[i];else add(a[i]);}printf("%d",n-top); }

?

轉載于:https://www.cnblogs.com/rir1715/p/6786275.html

總結

以上是生活随笔為你收集整理的【单调栈】最长不下降子序列变式的全部內容，希望文章能夠幫你解決所遇到的問題。

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