C. Sequence
time limit per test
memory limit per test
input
output
Little Petya likes to play very much. And most of all he likes to play the following game:
He is given a sequence of N integer numbers. At each step it is allowed to increase the value of any number by 1 or to decrease it by 1. The goal of the game is to make the sequence non-decreasing with the smallest number of steps. Petya is not good at math, so he asks for your help.
The sequence a is called non-decreasing if a1 ≤ a2 ≤ ... ≤ aN holds, where N
Input
The first line of the input contains single integer N (1 ≤ N ≤ 5000) — the length of the initial sequence. The following N lines contain one integer each — elements of the sequence. These numbers do not exceed 109
Output
Output one integer — minimum number of steps required to achieve the goal.
Sample test(s)
Input
5 3 2 -1 2 11
Output
4
Input
5 2 1 1 1 1
Output
1
思路：ff[]为原始序列，f[i]为原始序列的排序。dp[x][y]为把前x个数以j为标杆（0<=j<=y）变成非递减的最优值。
答案就是dp[m-1][m-1];
方程就是
dp[x][y]=min(dp[x][y-1],dp[x-1][y]+abs(ff[x]-f[y]))
优化空间。dp[j]为以第0-j个为标杆的把前i个数变成非递减的最小费用的最优值
dp[x]=min(dp[x-1],dp[x]+abs(ff[i]-f[x]));
盲点：为什么是用原始序列的排序为标杆得到的值就是最优的呢？以这些值以外的值为标杆就不可能得到更优的值吗？求解。
#include<iostream>#include<cstring>#include<algorithm>#include<cmath>using namespace std;const int mm=5004;long long f[mm],ff[mm],dp[mm];int main(){ int m; while(cin>>m) { for(int i=0;i<m;i++) { cin>>f[i];ff[i]=f[i]; } sort(f,f+m);///f为排完序的数列 memset(dp,0,sizeof(dp)); ///dp[j]为以第j个为标杆的把前i个数变成非递减的最小费用 for(int i=0;i<m;i++) for(int j=0;j<m;j++) { dp[j]+=abs(ff[i]-f[j]);///以f[j]为标杆 dp[j]=j&&dp[j]>dp[j-1]?dp[j-1]:dp[j]; ///更新值，dp[j]是以0-j为标杆中把前i个变成非递减的最小费用最优值 } cout<<dp[m-1]<<"\n"; }}