zcmimi's blog
查看原题

点击跳转

第一问:

数列中肯定有些是合法的,有些是不合法的

如果a_i-a_j < j-i就无法同时保留两者

那么a_i-a_j \ge j-i

所以a_i-i < a_j-j

b_i = a_i -i

b的最长不下降子序列长度就是最多能保留个数

第二问:

a变成严格单调上升等同于把b变成单调不降

唉,实在不会

https://pan.baidu.com/share/link?uk=2651016602&shareid=1490516411

#include<bits/stdc++.h>
#define inf 1000000000
#define ll long long
using namespace std;
int gi(){
    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;
}
void dp(){
    memset(mn,127,sizeof(mn));
    mn[0]=-1<<30;
    for(int i=1;i<=n;i++){
        int t=upper_bound(mn+1,mn+L+1,a[i])-mn;
        f[i]=t;
        L=max(L,t);
        mn[t]=min(mn[t],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=gi();
    for(int i=1;i<=n;i++)a[i]=gi()-i;
    a[++n]=1<<30;
    dp();
    solve();
    printf("%d\n%lld\n",n-f[n],g[n]);
    return 0;
}
LG 2501 [HAOI2006]数字序列
comment评论
Search
search