题目类型 DP
题目意思
给出一个 n (1 <= n <= 5000)个数的序列 问使这个序列变成非递减的操作数最少是多少
每个操作可以把 n 个数中的某一个 加1 或 减 1
例如给出3个数 3 2 3 -> 最优方案是把第2个数加1 变成 -> 3 3 3 最少操作数为 1
解题方法
dp[i][j] -> 前 i 个数变成一个以 j 为结尾的合法序列 所需的最少操作数
状态转移 dp[i][j] = min(dp[i][j], dp[i-1][k] + Cost(原来第i个位置上的数转换到j)) (1 <= k <= j)
即前i个数以j为结尾可以由 (前i-1个数以 比j小的数 结尾) 转移过来,这时还需要加上 从原来的第i个数转移到k的消耗
注意
由于输入的数的绝对值是小于等于 1e9 的 所以要把输入的数进行离散化, 递推的时候可以用滚动数组优化内存 避免 MLE
而且因为我们每次转移的时候需要的值是比 j 小的数中的最大值, 那么就可以用一个变量保存这个值然后递推时更新 不然会 TLE
附 :
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 5000 + 10;
const LL INF = 1LL<<62;
LL a[MAXN], b[MAXN];
LL dp[2][MAXN];
int main() {
int n;
while(cin>>n) {
for( int i=0; i<n; i++ ) {
cin>>a[i];
b[i] = a[i];
}
sort(b, b + n);
int tn = unique(b, b + n) - b; //离散化 输入的 n 个数
for( int i=0; i<tn; i++ ) dp[0][i] = abs(b[i] - a[0]), dp[1][i] = INF;
int now = 0;
for( int i=1; i<n; i++ ) {
LL t_min = INF;
for( int j=0; j<tn; j++ ) {
t_min = min(t_min, dp[now][j]);
dp[now^1][j] = min(dp[now^1][j], t_min + abs(b[j] - a[i]));
}
now ^= 1;
for( int j=0; j<tn; j++ ) dp[now^1][j] = INF;
}
LL n_min = INF;
for( int i=0; i<tn; i++ ) n_min = min(n_min, dp[now][i]);
cout<<n_min<<endl;
}
return 0;
}