E. Make It Increasing

首先讓$a_i=a_i?i$這樣可以是嚴(yán)格單增變成單調(diào)增。
參考官方題解
首先不難得出如果我們根據(jù)不同修改的位置分割成若干段，那么若干段是互不影響的，我們只需要求出每一個(gè)若干段修改次數(shù)的最小值。

如果當(dāng)前考慮l~r這一段，這里l和r都是不能修改的位置，我們要使得$a_l\le a_{l+1\to r?1}\le a_r$，對(duì)于原來(lái)不在此范圍內(nèi)的數(shù)一定需要修改，所以只需要考慮在此范圍內(nèi)的數(shù)如何修改的最少！實(shí)際上是選擇最長(zhǎng)的上升子序列，剩下的修改即可。而最長(zhǎng)上升子序列我們可以O(shè)(nlogn)解決。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<stack> #include<queue> #include<random> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=500010; int a[N],b[N],n,k; int main() {IO;int T=1;//cin>>T;while(T--){cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i];a[0]=-1e9,a[n+1]=2e9;for(int i=0;i<=n+1;i++) a[i]-=i;b[k+1]=n+1;b[0]=0;bool ok=1;int res=0;for(int i=0;i<=k;i++){int l=b[i],r=b[i+1];if(a[l]>a[r]){ok=0;break;}vector<int> lis;for(int j=l+1;j<r;j++)if(a[l]<=a[j]&&a[j]<=a[r]){auto pos=upper_bound(lis.begin(),lis.end(),a[j]);if (pos==lis.end()) lis.push_back(a[j]);else *pos=a[j];//這里會(huì)修改值}res+=(r-l-1)-lis.size();}if(!ok) res=-1;cout<<res<<'\n';}return 0; }

反思：md我知道那個(gè)小trick使得嚴(yán)格變成非嚴(yán)格，但是還是沒(méi)能運(yùn)用，還是見(jiàn)的太少，沒(méi)運(yùn)用這個(gè)小trick導(dǎo)致我的判斷不合法時(shí)尤為困難。

題解中的最長(zhǎng)上升子序列代碼好簡(jiǎn)潔，學(xué)習(xí)了！
貪心，考慮當(dāng)前的數(shù)，那么替換第一個(gè)大于它的數(shù)并不影響原來(lái)維護(hù)序列的單調(diào)性，而且答案不會(huì)更差！
要加油哦~

總結(jié)

以上是生活随笔為你收集整理的codeforces1437 E. Make It Increasing——最长上升子序列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。