[BZOJ1592] [Usaco2008 Feb]Making the Grade 路面修整（DP）

传送门

有个结论，每一个位置修改高度后的数，一定是原来在这个数列中出现过的数

因为最终结果要么不递增要么不递减，

不递增的话，

　　如果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; }

　　

上一篇：[BZOJ1574] [Usaco2009 Jan]地震损坏Damage（贪心 + dfs）

下一篇：[BZOJ3378] [Usaco2004 Open]MooFest 狂欢节（树状数组）

---

DP