题目大意：就是农夫要修一条路，现在要求这条路要么就是上升的，要么就是下降的，总代价为∑|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])；（用滚动数组就可以了）
另外这一题还有一个更快的解法，那就是用左式堆去解，这个我晚一点开一个新的随笔写好了
#include <iostream>
#include <functional>
#include <algorithm>
#define ABS(a,b) (a-b) > 0 ? (a-b):(b-a) using namespace std; static int road[];
static int new_road[];
static long long dp1[];
static long long dp2[]; int fcmop1(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}
int fcmop2(const void *a, const void *b)
{
return *(int *)b - *(int *)a;
} long long Search_Increase(const int);
long long Search_Decrease(const int); int main(void)
{
int n;
long long ans1, ans2;
while (~scanf("%d", &n))
{
for (int i = ; i < n; i++)
{
scanf("%d", &road[i]);
new_road[i] = road[i];
}
qsort(new_road, n, sizeof(int), fcmop1);
ans1 = Search_Increase(n);
printf("%lld", ans1);
/*
这题有问题，只用求不下降序列就可以了，如果求不上升序列会出错
qsort(new_road, n, sizeof(int), fcmop2);
ans2 = Search_Decrease(n);
printf("%lld\n", min(ans1, ans2));
*/
} return ;
} long long Search_Increase(const int n)
{
memset(dp1, , sizeof(dp1));
memset(dp2, , sizeof(dp2)); long long min_tmp, *dp_tmp = NULL, *p1 = dp1, *p2 = dp2, ans; for (int i = ; i < n; i++)
{
min_tmp = p1[];
for (int j = ; j < n; j++)
{
min_tmp = min(min_tmp, p1[j]);
p2[j] = (ABS(road[i], new_road[j])) + min_tmp;
}
dp_tmp = p1; p1 = p2; p2 = dp_tmp;
}
ans = p1[];
for (int i = ; i < n; i++)
ans = min(ans, p1[i]);
return ans;
} long long Search_Decrease(const int n)
{
memset(dp1, , sizeof(dp1));
memset(dp2, , sizeof(dp2)); long long min_tmp, *dp_tmp = NULL, *p1 = dp1, *p2 = dp2, ans; for (int i = ; i < n; i++)
{
min_tmp = p1[];
for (int j = ; j < n; j++)
{
min_tmp = min(min_tmp, p1[j]);
p2[j] = ABS(road[i], new_road[j]) + min_tmp;
}
dp_tmp = p1; p1 = p2; p2 = dp_tmp;
}
ans = p1[];
for (int i = ; i < n; i++)
ans = min(ans, p1[i]);
return ans;
}
另外这一题有BUG，那就是只用找不下降序列就可以了，两个都找会出错。。。。。
