P2501 [HAOI2006]数字序列 题解(dp+构造)

题目链接

题目思路

第一问就是构造\(b[i]=a[i]-i\)，然后求最长上升子序列

第二问就是假如\(b[l],b[r]\)满足，而且中间没有满足的情况，那么就前一段变为\(b[l]\)后一段变为\(b[r]\)

结论还是很显然的，但是写起来没那么方便，细节++

发现好多省选题目代码细节多的一批

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//typedef pair<int,int> pii;
#define fi first
#define se second
#define debug printf("aaaaaaaaaaa\n");
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1e9+7;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,a[maxn];
int b[maxn];
ll dp[maxn];
vector<int> vec[maxn];
ll pre[maxn],suf[maxn];
int len;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        a[i]=a[i]-i;
    }
    a[n+1]=inf-1;
    memset(dp,0x3f,sizeof(dp));
    memset(b,0x3f,sizeof(b));
    for(int i=1;i<=n+1;i++){
        int pos=upper_bound(b+1,b+1+n+1,a[i])-b;
        b[pos]=a[i];
        vec[pos].push_back(i);
        // 以i结尾的最长非严格上升子序列
        len=max(len,pos);
    }
    vec[0].push_back(0);
    a[0]=-inf;
    dp[0]=0;
    printf("%d\n",n-(len-1));
    for(int i=1;i<=len;i++){
        for(int j=0;j<vec[i].size();j++){
            int y=vec[i][j];
            for(int k=0;k<vec[i-1].size();k++){
                int x=vec[i-1][k];
                if(x>y) break;
                if(a[x]>a[y]) continue;
                for(int u=x;u<=y;u++){
                    if(u==x) pre[u]=0;
                    else pre[u]=pre[u-1]+abs(a[u]-a[x]);
                }
                suf[y+1]=0;
                for(int u=y;u>=x;u--){
                   suf[u]=suf[u+1]+abs(a[u]-a[y]);
                }
                ll mi=INF;
                for(int u=x;u<=y;u++){
                    mi=min(mi,pre[u]+suf[u+1]);
                }
                dp[y]=min(dp[y],dp[x]+mi);
            }
        }
    }
    printf("%lld\n",dp[n+1]);
    return 0;
}