「BZOJ1049」[HAOI2006] 数字序列
Description
现在我们有一个长度为n的整数序列A。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数，也不希望改变的幅度太大。
Input
第一行包含一个数n，接下来n个整数按顺序描述每一项的键值。
Output
第一行一个整数表示最少需要改变多少个数。 第二行一个整数，表示在改变的数最少的情况下，每个数改变的绝对值之和的最小值。
Sample Input
4
5 2 3 5
5 2 3 5
Sample Output
1
4
4
HINT
「数据范围」
90%的数据n<=6000。
100%的数据n<=35000。
保证所有数列是随机的。
题解
第一问减标号做最长不降子序列妥妥水过。。。
第二问思考无果。。。膜拜ydc神犇题解
http://pan.baidu.com/share/link?uk=2651016602&shareid=1490516411
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,L,cnt; int a[35005],mn[35005]; int f[35005],last[35005]; ll g[35005],s1[35005],s2[35005]; struct list{int to,next;}e[35005]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; } int find(int x) { int l=1,r=L,t=0; while(l<=r) { int mid=(l+r)>>1; if(mn[mid]<=x)t=mid,l=mid+1; else r=mid-1; } return t; } void dp() { memset(mn,127,sizeof(mn)); mn[0]=-1<<30; for(int i=1;i<=n;i++) { int t=find(a[i]); f[i]=t+1; L=max(L,t+1); mn[t+1]=min(mn[t+1],a[i]); } } void solve() { for(int i=n;i>=0;i--) { insert(f[i],i); g[i]=1LL<<60; } g[0]=0;a[0]=-1<<30; for(int x=1;x<=n;x++) for(int i=last[f[x]-1];i;i=e[i].next) { int p=e[i].to; if(p>x)break; if(a[p]>a[x])continue; for(int j=p;j<=x;j++) s1[j]=abs(a[p]-a[j]),s2[j]=abs(a[x]-a[j]); for(int j=p+1;j<=x;j++) s1[j]+=s1[j-1],s2[j]+=s2[j-1]; for(int j=p;j<x;j++) g[x]=min(g[x],g[p]+s1[j]-s1[p]+s2[x]-s2[j]); } } int main() { n=read(); for(int i=1;i<=n;i++)a[i]=read()-i; a[++n]=1<<30; dp(); solve(); printf("%d\n%lld\n",n-f[n],g[n]); return 0; } |
计数器 9824609
OI 课件=>
OI 课件=>
如果不随机怎么办？