\(\texttt{离散化+滚动数组}\)

Idea

\(dp[i][j]\)表示前i个数以\(a[j]\)为结尾的满足要求的最少的操作，可是题目给的最大数是\(10^9\)，二维数组的\(j\)元素不可能开这么大，所以需要离散化一下，改成前i个数以第\(j\)个数为结尾的满足要求的最少的操作。

\(dp[i][j]=min(dp[i][j],\text{第i-1个位置前j个数的最小操作}+abs(b[j]-a[i]))\) \(b\)数组是原来输入的\(a\)数组排好序且离散化之后的数组

因为\(b\)数组是从小到大排好序的，所以在第\(i\)个位置时第\(j\)个数肯定比\(i-1\)个位置的前j个数要大。

最后\(dp[5000][5000]\)也不能存下，那么这个二维数组就要滚一下了。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<string>
#include<queue>
#define ll long long
#define maxn 100001
#define mod 998244353
#define eps 1e-6
#define pi acos(-1.0)
#define de(x) ((x)*(x))
using namespace std; 
inline int read(){
    int x=0,f=1; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const ll inf=1ll<<62;
ll dp[2][5007],a[5007],b[5007];
int main(){
    ll n=read();
    for(ll i=1;i<=n;i++){
        a[i]=read();
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    ll tot=unique(b+1,b+n+1)-b-1;//离散化
    dp[1][1]=inf;
    for(ll i=1;i<=tot;i++){
        dp[1&1][i]=fabs(b[i]-a[1]);
        dp[2&1][i]=inf;
    }
    for(ll i=2;i<=n;i++){
        ll minn=inf;
        for(ll j=1;j<=tot;j++){
            minn=min(minn,dp[(i-1)&1][j]);//取上一个位置中前j颗不同高度的树中花费最小
            dp[i&1][j]=min(dp[i&1][j],minn+abs(b[j]-a[i]));//当前位置等于上一个位置中前j颗树花费最小+这个位置是第j颗树的花费
        }
        for(ll j=1;j<=tot;j++) dp[(i+1)&1][j]=inf;
    }
    ll ans=inf;
    for(ll i=1;i<=tot;i++) ans=min(ans,dp[n&1][i]);//取最后一个位置是第j颗树是花费最小
    printf("%lld",ans);
    return 0;
}

CF 13C Sequence

原文：https://www.cnblogs.com/cbyyc/p/11475068.html