5501 环路运输 0x50「动态规划」例题
描述
在一条环形公路旁均匀地分布着N座仓库，编号为1~N，编号为 i 的仓库与编号为 j 的仓库之间的距离定义为 dist(i,j)=min(|i-j|,N-|i-j|)，也就是逆时针或顺时针从 i 到 j 中较近的一种。每座仓库都存有货物，其中编号为 i 的仓库库存量为 A_i。在 i 和 j 两座仓库之间运送货物需要的代价为 A_i+A_j+dist(i,j)。求在哪两座仓库之间运送货物需要的代价最大。1≤N≤10^6，1<=Ai<=10^7。
输入格式
第一行一个整数N，第二行N个整数A1~AN。
输出格式
一个整数，表示最大代价。
样例输入
5 1 8 6 2 5
样例输出
15
题意：
n个仓库环形排列，每个仓库有一个库存量。i和j仓库之间运送货物的代价是Ai + Aj + dist(i, j)。dist(i, j) = min(|i - j|, N - |i - j|)
要求哪两个仓库之间运送货物代价最大。
思路：
在1和n之间把环断开，复制一倍接在末尾。原来环形路上的两个点i和j，如果i - j <= N / 2，那么新的公路上，他们的代价仍然是Ai + Aj + i - j
如果i - j > N / 2, 那么在原来环形路上就要反方向，相当于在新的道路上，i和j+N之间运送货物。代价就是Ai + Aj+n + j + N - i
所以原问题就可以转化为：长度为2N的直线公路上，满足1 <= j < i <= 2N 并且 i - j <= N / 2 的仓库i和j之间运送货物，使得代价 Ai + Aj + i - j最大
我们可以枚举i，找到对应的Aj - j最大的j。
枚举i的过程中如果继续枚举j，显然会超时。可以考虑使用单调队列进行优化。
我们可以比较k和j， k < j < i并且Ak - k < Aj - j ， 那么对于所有大于等于i的右端点，k永远不会成为最优选择。因为不但Ak - k较小，而且k离i更远，更容易超过N/2的限制，即j的生存能力比k强。所以j出现之后，k就是一个完全无用的位置。
能够成为最优选择的策略集合一定是一个“下标位置递增，对应的Ai - i也递增”的序列。
那么我们从前向后扫描，对于每个i 执行3 个步骤：
1.判断队头决策与i的距离是否超出N/2的限制，若超出则出队。
2.此时的队头元素就是右端点为i时，左端点j的最优选择。
3.删除队尾决策，队尾对应的Ak - k 小于Ai- i， 把i作为一个新的决策入队。
可以把原来的算法优化至O(n)
1 //#include <bits/stdc++.h> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<stdio.h> 6 #include<cstring> 7 #include<vector> 8 #include<map> 9 10 #define inf 0x3f3f3f3f 11 using namespace std; 12 typedef long long LL; 13 14 int n; 15 const int maxn = 1e6 + 5; 16 int a[maxn * 2], q[maxn * 2]; 17 18 int main() 19 { 20 scanf("%d", &n); 21 for(int i = 1; i <= n; i++){ 22 scanf("%d", &a[i]); 23 } 24 for(int i = n + 1; i <= 2 * n; i++){ 25 a[i] = a[i - n]; 26 } 27 28 //memset(dp, 0, sizeof(dp)); 29 int l = 1, r = 1, ans = 0; 30 q[1] = 1; 31 for(int i = 2; i <= 2 * n; i++){ 32 while(l <= r && q[l] < i - n / 2)l++; 33 ans = max(ans, a[i] + a[q[l]] + i - q[l]); 34 while(l < r && a[i] - i >= a[q[r]] - q[r]) r--; 35 q[++r] = i; 36 } 37 38 printf("%d\n", ans); 39 return 0; 40 }