CF-13C. Sequence(DP)是什么？

本文共计687个文字，预计阅读时间需要3分钟。

C. 序列时间限制/测试内存限制/输入/输出小佩佳非常喜欢玩游戏。尤其是他最喜欢的以下游戏：他得到一个由N个整数组成的序列。在每一步，允许他增加序列中的某个数。

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 a₁ ≤ a₂ ≤ ... ≤ a_N 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 10⁹

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"; }}