题目描述

给定一个长度为n的数列{ai}（i=1,2,3,...,n)。

定义满足ai<=ai+1为单调不减数列。

现在你可以对原数列进行如下两种操作：

1）将数列中任意1个数字加1；

2）将数列中任意1个数字减1.

问：最少操作多少次可以将原数列变为单调不减数列。

输入

单组数据输入，每组数据第一行一个整数n（0<n<5555），

接下来一行n个整数ai（|ai|<1e9，每个数的绝对值小于1e9）。

输出

输出最少操作数。

样例输入

44 3 2 1

样例输出

4 哇！！比赛的时候心态都崩了，被这个题卡了两个多小时。。还是没做出来。 思路：思路比较简单吧！ dp，dp[i][j];代表将前i个数转换为最大数为b[j]的单调不减序列的最小代价；

1 #include
     
       2 #include
      
        3 #include
       
         4  5 using namespace std; 6 typedef long long LL; 7 const LL INF = 3e9 + 10; 8 const int maxn = 5600; 9 LL n, ans, dp[maxn],a[maxn], b[maxn];10 int main()11 {12     ios::sync_with_stdio(false);13     while (cin >> n) {14         memset(dp, 0, sizeof(dp));15         for (int i = 1; i <= n; i++) {16             cin >> a[i]; b[i] = a[i];17         }18         sort(b + 1, b + n + 1);19         for (int i = 1; i <= n; i++) {20             for (int j = 1; j <= n; j++) {21                 dp[j] += abs(a[i] - b[j]);22                 if (j > 1)dp[j] = min(dp[j], dp[j - 1]);23             }24         }25         cout << dp[n] << endl;26     }27     return 0;28 }