作者：HVV_Ha8m | 来源：互联网 | 2023-01-31 18:32
聪明的修路方案
题目大意：就是农夫要修一条路，现在要求这条路要么就是上升的，要么就是下降的，总代价为∑|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
2 #include
3 #include
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 )
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\n", 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 )
58 {
59 min_tmp = p1[0];
60 for (int j = 0; 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 )
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 )
81 {
82 min_tmp = p1[0];
83 for (int j = 0; 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 )
92 ans = min(ans, p1[i]);
93 return ans;
94 }
另外这一题有BUG，那就是只用找不下降序列就可以了，两个都找会出错。。。。。
京公网安备 11010802041100号