题目大意：就是农夫要修一条路，现在要求这条路要么就是上升的，要么就是下降的，总代价为∑|a[i]-b[i]|，求代价最低的修路方案， (0 ≤ β≤ 1,000,000,000) ， (1 ≤ N ≤ 2,000)
这一题百分百就是DP了，为什么？我们现在就是要让cost最小，但是我们不知道cost应该怎么才能最小。
我们可以这么想，因为序列总是上升或者下降的，我们可以考虑上升的情况，假设前几个数组成的最大值为β，我们要考虑从0-β的改变值，然后不断推到第n个序列。
显然，这样的复杂度为0（Nβ^2），当然这样的复杂度显然是出事的。
现在我们想着优化这个东西，我们可以这么想，如果我们像之前那样扫描的话，那么其实我们忽略了一个很重要的事实，就是在变到α(α<β)，其实对于α+1~β之内不会对α造成影响，于是我们可以用一个最小值的临时变量储存在α之前的最小值，用这个更新dp即可，那样就少了一次扫β的复杂度
复杂度变为O(Nβ);
但是如果仅仅是这样的话，绝对是TLE，因为β实在是太大了。
那么我们就要用到离散化的思想，把β投影到有限区域中，既然β是大小的函数，那么我们把可以这样对应：我们只用把新的序列按从小到大排列，然后只对下标进行查找就可以了，这样我们就把解的空间变到下标中了。
最后状态转移方程：dp[i-1][j]=ABS(a[i]-b[j])+min(dp[i-1][j])；（用滚动数组就可以了）
另外这一题还有一个更快的解法，那就是用左式堆去解，这个我晚一点开一个新的随笔写好了
1 #include <iostream> 2 #include <functional> 3 #include <algorithm> 4 #define ABS(a,b) (a-b) > 0 ? (a-b):(b-a) 5 6 using namespace std; 7 8 static int road[2000]; 9 static int new_road[2000]; 10 static long long dp1[2000]; 11 static long long dp2[2000]; 12 13 int fcmop1(const void *a, const void *b) 14 { 15 return *(int *)a - *(int *)b; 16 } 17 int fcmop2(const void *a, const void *b) 18 { 19 return *(int *)b - *(int *)a; 20 } 21 22 long long Search_Increase(const int); 23 long long Search_Decrease(const int); 24 25 int main(void) 26 { 27 int n; 28 long long ans1, ans2; 29 while (~scanf("%d", &n)) 30 { 31 for (int i = 0; i < n; i++) 32 { 33 scanf("%d", &road[i]); 34 new_road[i] = road[i]; 35 } 36 qsort(new_road, n, sizeof(int), fcmop1); 37 ans1 = Search_Increase(n); 38 printf("%lld", ans1); 39 /* 40 这题有问题，只用求不下降序列就可以了，如果求不上升序列会出错 41 qsort(new_road, n, sizeof(int), fcmop2); 42 ans2 = Search_Decrease(n); 43 printf("%lld ", min(ans1, ans2)); 44 */ 45 } 46 47 return 0; 48 } 49 50 long long Search_Increase(const int n) 51 { 52 memset(dp1, 0, sizeof(dp1)); 53 memset(dp2, 0, sizeof(dp2)); 54 55 long long min_tmp, *dp_tmp = NULL, *p1 = dp1, *p2 = dp2, ans; 56 57 for (int i = 0; i < n; i++) 58 { 59 min_tmp = p1[0]; 60 for (int j = 0; j < n; j++) 61 { 62 min_tmp = min(min_tmp, p1[j]); 63 p2[j] = (ABS(road[i], new_road[j])) + min_tmp; 64 } 65 dp_tmp = p1; p1 = p2; p2 = dp_tmp; 66 } 67 ans = p1[0]; 68 for (int i = 1; i < n; i++) 69 ans = min(ans, p1[i]); 70 return ans; 71 } 72 73 long long Search_Decrease(const int n) 74 { 75 memset(dp1, 0, sizeof(dp1)); 76 memset(dp2, 0, sizeof(dp2)); 77 78 long long min_tmp, *dp_tmp = NULL, *p1 = dp1, *p2 = dp2, ans; 79 80 for (int i = 0; i < n; i++) 81 { 82 min_tmp = p1[0]; 83 for (int j = 0; j < n; j++) 84 { 85 min_tmp = min(min_tmp, p1[j]); 86 p2[j] = ABS(road[i], new_road[j]) + min_tmp; 87 } 88 dp_tmp = p1; p1 = p2; p2 = dp_tmp; 89 } 90 ans = p1[0]; 91 for (int i = 1; i < n; i++) 92 ans = min(ans, p1[i]); 93 return ans; 94 }
另外这一题有BUG，那就是只用找不下降序列就可以了，两个都找会出错。。。。。
