題目鏈接：http://www.lydsy.com:808/JudgeOnline/problem.php?id=1049

題意：給出一個(gè)數(shù)列A，要求：（1）修改最少的數(shù)字使得數(shù)列嚴(yán)格遞增；（2）在（1）的基礎(chǔ)上使得修改的絕對(duì)值之和最小。

思路：對(duì)于第一問(wèn)看起來(lái)像是求最長(zhǎng)上升子 列，其實(shí)不是。我們想，若對(duì)于i<j，j能由i轉(zhuǎn)移過(guò)來(lái)，那么需滿足A[j]-A[i]>=j-i才行，這樣我們發(fā)現(xiàn)只要A[j]-j>=A[i]-i即可。因此令A(yù)[i]=A[i]-i，這樣求LIS即可。對(duì)于第二問(wèn)，若i<j且j由i轉(zhuǎn)移過(guò)來(lái)，那么[i+1,j-1]之間 的數(shù)字或者大于A[j]或者小于A[i]，最后這段區(qū)間的數(shù)字必然是前面一段修改為A[i]后面一段修改為A[j]。因此，記錄每個(gè)位置j由哪些前面的位置轉(zhuǎn)移過(guò)來(lái)，直接暴力枚舉前面的位置i即可。然后對(duì)于[i+1,j-1]，暴力枚舉中間的分界點(diǎn)。

?

int a[N],b[N],c[N],n,f[N]; vector<int> V[N]; int S[N],M;int find(int x) {int low=1,high=M,mid;while(low<=high){mid=(low+high)>>1;if(b[mid]==x) return mid;if(b[mid]<x) low=mid+1;else high=mid-1;} }void add(int x,int y) {while(x<=n) upMax(S[x],y),x+=x&-x; }int get(int x) {int ans=0;while(x) upMax(ans,S[x]),x-=x&-x;return ans; }int Ans;void deal1() {int i;a[++n]=INF;FOR1(i,n) b[i]=a[i];sort(b+1,b+n+1);M=unique(b+1,b+n+1)-(b+1);FOR1(i,n) c[i]=find(a[i]);Ans=0;FOR1(i,n) {f[i]=get(c[i])+1;add(c[i],f[i]);upMax(Ans,f[i]);}PR(n-Ans); }i64 sum1[N],sum2[N],dp[N];void deal2() {int i,j,k,t;V[0].pb(0);FOR1(i,n) V[f[i]].pb(i),dp[i]=inf;a[0]=-INF; dp[0]=0;FOR1(i,n) {FOR0(j,SZ(V[f[i]-1])){k=V[f[i]-1][j];if(k>i) break;if(a[k]>a[i]) continue;for(t=k;t<=i;t++) sum1[t]=abs(a[t]-a[k]),sum2[t]=abs(a[t]-a[i]);for(t=k+1;t<=i;t++) sum1[t]+=sum1[t-1],sum2[t]+=sum2[t-1];for(t=k;t<i;t++) upMin(dp[i],dp[k]+sum1[t]+sum2[i]-sum2[t]);}}PR(dp[n]); }int main() {RD(n);int i;FOR1(i,n) RD(a[i]),a[i]-=i;deal1(); deal2(); }

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/jianglangcaijin/p/3799480.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 1049 数字序列（LIS）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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