就DP而言这个题不算难，但是难就难在贪心，还有离散化的思想上
题目大意：n个土堆，问你最少移动多少单位的图，可以使得这n个土堆变成单调的
dp[i][j]表示前i个土堆高变为j时最优值
dp[i][j] = abs(j - a[i]) + min(dp[i-1][k])
到这里就有问题了，k遍历起来有多大，是吧，没法想‘？
所以搜了题解才知道:贪心的思想：如果选了一个c[i]得到最优值，那么必然可以通过转换，使得最终序列花费不变，并全部用原序列的数。
也有一个大佬的证明
假设存在a s <b i <=b i+1 <=⋯<=b j <a s+1 as<bi<=bi+1<=⋯<=bj<as+1
情况一：如果这些b都相等,那么把这些b都改成a s as 或者a s+1 as+1 肯定会有一种更优。
情况二：如果不全相等,那么肯定存在 b p b p+1 b p+2 ⋯b q bp bp+1 bp+2⋯bq ,他们的值相等,那么把他们移到左边的关键点或者右边的关键点,肯定有一种会更加优. 不断这样移动,最后就变成情况一了。
综上至少存在一种最优方案,最终的所有数都是原来的某个数。
因此可以离散化之后做dp,dp[i][j]表示把前i个数变成单调增(不严格)且第i个数变成原来第j大的数的最小代价。
这样关于k的遍历就好了但是我们真的还要去遍历k吗，只是一个最小值而已，只要记录一下不就好了
#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
#define inf (1 << 30)
using namespace std;
const int maxn = 2e3 + 2e2;
long long dp[maxn][maxn];
int a[maxn],b[maxn];
void init()
{
memset(dp,0,sizeof(dp));
}
//dp[i]表示前i个的最小花费
int main()
{
int n;
while(~scanf("%d",&n))
{
init();
for(int i = 1;i <= n;i++)
{
scanf("%d",&a[i]);
b[i] = a[i];
}
sort(b+1,b+1+n);
for(int i = 1;i <= n;i++)
{
long long m = dp[i-1][1];
for(int j = 1;j <= n;j++)
{
m = min(m,dp[i-1][j]);//m记录的是第i-1个数小于等于j时最小值
dp[i][j] = abs(a[i] - b[j]) + m;//这里层次记录为了i+1个数做铺垫
}
}
long long ans = inf;
for(int j = 1;j <= n;j++)
{
ans = min(ans,dp[n][j]);
}
printf("%lld\n",ans);
}
return 0;
}
