把一个序列转换成非严格递增序列的最小花费 POJ 3666

时间：2021-06-24 06:46:37
 //把一个序列转换成非严格递增序列的最小花费 POJ 3666

 //dp[i][j]:把第i个数转成第j小的数，最小花费

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <algorithm>

 #include <vector>

 #include <math.h>

 // #include <memory.h>

 using namespace std;

 #define LL long long

 typedef pair<int,int> pii;

 const int inf = 0x3f3f3f3f;

 const LL MOD =100000000LL;

 const int N = +;

 const double eps = 1e-;

 void fre() {freopen("in.txt","r",stdin);}

 void freout() {freopen("out.txt","w",stdout);}

 inline int read() {int x=,f=;char ch=getchar();while(ch>''||ch<'') {if(ch=='-') f=-; ch=getchar();}while(ch>=''&&ch<='') {x=x*+ch-'';ch=getchar();}return x*f;}

 int a[N],b[N];

 LL dp[N][N];

 int main(){

     int n;

     scanf("%d",&n);

     for(int i=;i<=n;i++){

         scanf("%d",&a[i]);

         b[i]=a[i];

     }

     sort(b+,b++n);

     for(int i=;i<=n;i++){

         dp[][i]=abs(a[]-b[i]);

     }

     for(int i=;i<=n;i++){

         LL minn=1e18;

         for(int j=;j<=n;j++){

            minn=min(minn,dp[i-][j]);

            dp[i][j]=minn+abs(a[i]-b[j]);

         }

     }

     LL ans=1e18;

     for(int i=;i<=n;i++){

         ans=min(ans,dp[n][i]);

     }

     cout<<ans<<endl;

     return ;

 }

相关文章