题意：
给定n个数，问你将他们修改成非增或非减序列的最小花费。最小花费的定义是
假设原数组为 a[1] a[2] a[3] …. a[n]
修改后数组为 b[1] b[2] b[3] …. b[n]
那么最小花费为|a[1]-b[1]|+|a[2]-b[2]|+| a[3] – b[3] |+…..| a[n] – b[n] |.
思路：
线性结构上的动态规划 定义状态d[i][j] 表示 前i-1个数字已经是最小花费 现在把第i个数修改成b[j] 修改完成后前i个数总共最少需要的花费是多少
状态转移 见代码
或者看这个链接：
值得注意的是 不知道是我理解错题意还是有些人做错了 弱感觉他们只考虑了非减的情况 但是却AC了。他们的代码是不能解决 3 2 1 这个样例的…弱以为应该输出0才对啊；
code:
#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;const int maxn = 2005;int n;int a[maxn], b[maxn];int dp[maxn][maxn];bool cmp1(int a1, int a2){return a1 > a2;}void init(){int tmp;for(int i = 1; i <= n; i++){scanf("%d",&tmp);a[i] = b[i] = tmp;}sort(b+1, b+n+1);}void solve(){memset(dp,0,sizeof(dp));for(int i = 1; i <= n; i++){dp[1][i] = abs(a[1] – b[i]);}for(int i = 2; i <= n; i++){int min_cost = dp[i-1][1];for(int j = 1; j <= n; j++){min_cost = min(min_cost, dp[i-1][j]);dp[i][j] = min_cost + abs(a[i] – b[j]);}}int ans1 = dp[n][1];for(int i = 2; i <= n; i++){ans1 = min(ans1, dp[n][i]);}sort(b+1, b+n+1, cmp1);memset(dp,0,sizeof(dp));for(int i = 1; i <= n; i++){dp[1][i] = abs(a[1] – b[i]);}for(int i = 2; i <= n; i++){int min_cost = dp[i-1][1];for(int j = 1; j <= n; j++){min_cost = min(min_cost, dp[i-1][j]);dp[i][j] = min_cost + abs(a[i] – b[j]);}}int ans2 = dp[n][1];for(int i = 2; i <= n; i++){ans2 = min(ans2, dp[n][i]);}printf("%d\n",min(ans1, ans2));}int main(){while(scanf("%d",&n) != EOF){init();solve();}return 0;}/*33 2 1*/
，谦受益，满招损。
