codevs3250 操作序列

题目描述 Description

Petya是一个非常好玩孩子。他很无聊，因此他开始玩下面的游戏：

他得到一个长度为N的整数序列，他会对这些数字进行操作，他可以把某个数的数值加1或者减1(当然他可以对同一个数操作很多次)。他的目的是使得数列非递减，即在修改之后，数列满足a1≤a2≤...≤aN 。

请你告诉他，他最少要操作多少次。

输入描述 Input Description

第1行一个整数n。

第2行n个整数 a1、a2、……、an，每两个整数之间用一个空格隔开

输出描述 Output Description

输出只有一行1个整数，表示最少的操作次数。

样例输入 Sample Input

3 2 -1 2 11

样例输出 Sample Output

数据范围及提示 Data Size & Hint

对于30%的数据 1≤n≤60 的绝对值不超过

对于 60%的数据 1≤n≤200

对于100%的数据1≤n≤5000 的绝对值不超过。

/*

同修路

*/

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<algorithm>

#include<cmath>

#define ll int

using namespace std;

const int maxn = ;

const ll inf = ~0U>>;

struct orz{

    ll p;

    ll v;

};

bool cmp(orz a,orz b){

    return a.v < b.v;

}

ll n,k,a[maxn],dp[maxn][maxn],ans;

orz b[maxn];

inline ll read(){

    char ch=getchar();

    ll f=,x=;

    while(!(ch>=''&&ch<='')){if(ch=='-')f=-;ch=getchar();};

    while(ch>=''&&ch<=''){x=x*+(ch-'');ch=getchar();};

    return x*f;

}

int main(){

    n = read();

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

        a[i] = b[i].v = read();

        b[i].p = i;

    }

    sort(b+,b++n,cmp);

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

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

            dp[i][j] = inf;

        }

    }

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

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

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

            dp[i][j] = min(dp[i][j],dp[i-][j]+abs(b[j].v-a[i]));

        }

    }

    cout<<dp[n][n]<<endl;

    return ;

}

巴特西

codevs3250 操作序列

最新文章

热门文章