题目链接
凯大佬的博客
题意:
给定一个长度为 n 的非负整数序列 a[1..n]。
你每次可以花费 1 的代价给某个 a[i] 加1或者减1。
求最少需要多少代价能将这个序列变成一个不上升序列（有的题目是非递减的,或者严格递减的等等）。
这三个题目都是类似的,只是问法不一样,严格问题的凯爷的博客说的已经很明确了.对于hiho上那个题,因为数据量太大（n^2）是过不了的,大佬们的解法
我还没看懂,涉及到一些知识点,还在继续挖坑.
对于这个题目的话,首先应该想到变换成附和满足题意的序列一定是一开始就已经存在的.这样才能代价最小。
dp[i][j]表示前i个数,以b[j]结尾的最小代价,dp[i][j]=min(dp[i][j-1],dp[i-1][j]+abs(a[i]-b[j]))，这里最好是降一下维或者进行滚动数组。
#include<bits/stdc++.h> #define Ri(a) scanf("%d", &a) #define Rl(a) scanf("%lld", &a) #define Rf(a) scanf("%lf", &a) #define Rs(a) scanf("%s", a) #define Pi(a) printf("%d\n", (a)) #define Pf(a) printf("%lf\n", (a)) #define Pl(a) printf("%lld\n", (a)) #define Ps(a) printf("%s\n", (a)) #define W(a) while(a--) #define CLR(a, b) memset(a, (b), sizeof(a)) #define MOD 1000000007 #define inf 0x3f3f3f3f #define exp 0.00000001 #define pii pair<int, int> #define mp make_pair #define pb push_back using namespace std; typedef long long ll; const int maxn=1e5+10; ll a[maxn],b[maxn]; ll dp[maxn]; int n; int main() { Ri(n); for(int i=1;i<=n;i++) { Rl(a[i]); b[i]=a[i]; } sort(b+1,b+1+n); CLR(dp,0); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(j==1) dp[j]+=abs(a[i]-b[j]); else { dp[j]=min(dp[j-1],dp[j]+abs(a[i]-b[j])); } } } Pl(dp[n]); return 0; } Marcus-Bao 认证博客专家 推荐系统 ACM算法竞赛 机器学习 本科毕业于国内知名四非大学，现中国科学院大学博士生，中国科学院计算技术研究所vipl实验室，老年ACM铁牌退役选手，喜欢算法竞赛，会点数据结构和算法，熟悉c++，python等；现阶段研究方向主要为机器学习与数据挖掘，比较关注推荐系统，发过顶会，炼过丹，平时博客主要记录些关于算法、数据结构，人工智能技术以及平时看的论文总结分享等，欢迎大家关注我，一起多多交流共同进步！
