首页 > 代码库 > BZOJ 1049 数字序列(LIS)
BZOJ 1049 数字序列(LIS)
题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=1049
题意:给出一个数列A,要求:(1)修改最少的数字使得数列严格递增;(2)在(1)的基础上使得修改的绝对值之和最小。
思路:对于第一问看起来像是求最长上升子 列,其实不是。我们想,若对于i<j,j能由i转移过来,那么需满足A[j]-A[i]>=j-i才行,这样我们发现只要A[j]-j& gt;=A[i]-i即可。因此令A[i]=A[i]-i,这样求LIS即可。对于第二问,若i<j且j由i转移过来,那么[i+1,j-1]之间 的数字或者大于A[j]或者小于A[i],最后这段区间的数字必然是前面一段修改为A[i]后面一段修改为A[j]。因此,记录每个位置j由哪些前面的位 置转移过来,直接暴力枚举前面的位置i即可。然后对于[i+1,j-1],暴力枚举中间的分界点。
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();}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。