传送门
有个结论，每一个位置修改高度后的数，一定是原来在这个数列中出现过的数
因为最终结果要么不递增要么不递减，
不递增的话，
如果x1 >= x2那么不用动，如果x1 < x2，把x1变成x2的代价最小
不递减同理
输入数组a后，把a数组复制一份放到b中，并将b排序
f[i][j]表示前i个，当前修改为b[j]的最优解
dp的时候前缀和优化一下即可
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 2001 #define abs(x) ((x) < 0 ? (x) : (x)) #define min(x, y) ((x) < (y) ? (x) : (y)) int n, ans = ~(1 << 31); int a[N], b[N], f[N][N][2]; //f[i][j]表示前i个数，第i个数为b[j]的最优解 //0表示不下降，1表示不上升 inline int read() int main() sum = ~(1 << 31); for(j = n; j >= 1; j) } for(i = 1; i <= n; i++) ans = min(ans, min(f[n][i][0], f[n][i][1])); printf("%d\n", ans); return 0; }
上一篇：[BZOJ4992] [Usaco2017 Feb]Why Did the Cow Cross the Road（spfa）
下一篇：[BZOJ1595] [Usaco2008 Jan]人工湖（单调栈）
DP
