首页 > 代码库 > codevs3250 操作序列
codevs3250 操作序列
题目描述 Description
Petya是一个非常好玩孩子。他很无聊，因此他开始玩下面的游戏：
他得到一个长度为N的整数序列，他会对这些数字进行操作，他可以把某个数的数值加1或者减1(当然他可以对同一个数操作很多次)。他的目的是使得数列非递减，即在修改之后，数列满足a1≤a2≤...≤aN 。
请你告诉他，他最少要操作多少次。
输入描述 Input Description
第1行一个整数n。
第2行n个整数 a1、a2、……、an，每两个整数之间用一个空格隔开
输出描述 Output Description
输出只有一行1个整数，表示最少的操作次数。
样例输入 Sample Input
5
3 2 -1 2 11
样例输出 Sample Output
4
数据范围及提示 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 intusing namespace std;const int maxn = 5005;const ll inf = ~0U>>1;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=1,x=0; 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 main(){ n = read(); for(int i = 1;i <= n;i++){ a[i] = b[i].v = read(); b[i].p = i; } sort(b+1,b+1+n,cmp); for(int i = 1;i <= n;i++){ for(int j = 0;j <= n;j++){ dp[i][j] = inf; } } for(int i = 1;i <= n;i++){ for(int j = 1;j <= n;j++){ dp[i][j] = min(dp[i][j],dp[i][j-1]); dp[i][j] = min(dp[i][j],dp[i-1][j]+abs(b[j].v-a[i])); } } cout<<dp[n][n]<<endl; return 0;}
codevs3250 操作序列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。