原题链接
给定一个数轴, 数轴上有一些点, 第 \(i\) 个点离起点的距离是 \(S_i\), 取走它要消耗 \(A_i\) 的代价, 同时在数轴上每移动一格要 \(1\) 的代价, 路线只能从数轴原点走到最后一个取走的点的位置再走回去, 问 \(\forall k\in [1, n]\) 取走 \(k\) 个点的代价最大值
算法1
设 \(f[i][j]\) 表示前 \(i\) 个点, 一共取了 \(j\) 的最大价值, 那么也就有
\[f[i][j] = \max(f[i-1][j], \max_{k=j-1}^{i-1}f[k][j-1]+A_i+2\times (S_i-S_k)) \]转移的时间复杂度是 \(O(n^3)\), 空间复杂度 \(O(n^2)\), 期望得分 \(40\rm {pts}\), 实际得分 \(40\rm {pts}\)
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int N = 1e3 + 10;
long long f[N][N];
struct node{
int s, a;
}p[N];
int n;
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", &p[i].s);
}
for(int i = 1; i <= n; i++){
scanf("%d", &p[i].a);
}
for(int i = 1; i <= n; i++){
f[i][0] = 2 * p[i].s;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= i; j++){
for(int k = j-1; k < i; k++){
f[i][j] = max(f[i][j], max(f[i-1][j], f[k][j-1] + p[i].a + 2 * (p[i].s - p[k].s)));
}
}
}
for(int i = 1; i <= n; i++){
printf("%lld\n", f[n][i]);
}
return 0;
}
算法2
这个式子似乎没有办法优化?换一个方法
考虑上面的 DP, 难以优化的一个重要原因就是考虑到距离的计算, 所以现在直接忽略距离的限制, 那么取 \(k\) 个点的情况就是按 \(A_i\) 排序的前 \(k\) 个, 但是如果加上距离的限制, 这个答案可能就不对了, 考虑尝试对答案进行微调以满足性质
下面讨论的"前面"等关于位置的词都是在按 \(A_i\) 排序的情况下讨论的
考虑舍掉一个最小的 \(A_i\) 以换取最大值, 也就是取走 \(\forall k\in[i, n]\) 之中 \(2\times S_k + a_k\) 的最大值(第 \(i\) 个位置的这个值我们记为 \(g[i]\)), 可以证明, 只需要舍去最小值就能得到可能的最大值, 继续舍去只会更劣
假设舍掉了 \(A_i, A_{i-1}\), 换取了第 \(j\) 个和第 \(k\) 个点, 那么 \(j\) 和 \(k\) 两个点的贡献只会是 \(2\times \max(S_j, S_k) + A_j + A_k\), 不妨假设 \(g[i]=2\times S_j + A_j\), 否则可以调换 \(j\) 和 \(k\), 那么上面就相当于 \(g[i] + A_k\), \(A_k\) 显然劣于 \(A_{i-1}\), 因为是从大到小排序的, 所以多取任何一个都必定是亏的, 要求最大值只要舍掉最后一个即可
最后的答案只要在直接取前 \(i\) 个的情况和上面舍去的情况取 \(\max\) 就可以了
还有一个问题: 如果我们舍掉了第 \(i\) 个取了后面的一个, 但是取的这 \(i\) 个点中距离最大值在前 \(i-1\) 个之中, 似乎会导致问题(舍去的情况下我们的距离值只取了补回去的那个而没有在所有选的点中取\(\max\)), 接下来证明这种情况下, 舍去的情况一定不会被选:
如果距离最大值在前 \(i\) 个之中, 那么多取的那个点, 距离一定小于前面的距离最大值, 并且代价也一定小于前面 \(i\) 个点的任何一个, 那么舍去一定比不舍去更劣, 所以不会产生上面谈到的问题
只要用前缀和优化一下就可以 \(O(n)\) 解决这个问题, 期望得分 \(100\rm {pts}\), 实际得分 \(100\rm {pts}\)
代码如下:
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
struct node{
int s, a;
}p[N];
long long sum[N];
long long pre[N];
long long suf[N];
bool cmp(node a, node b){
return a.a > b.a;
}
int main(){
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &p[i].s);
for(int i = 1; i <= n; i++)
scanf("%d", &p[i].a);
sort(p + 1, p + 1 + n, cmp);
for(int i = 1; i <= n; i++)
sum[i] = sum[i-1] + p[i].a;
for(int i = 1; i <= n; i++)
pre[i] = max(pre[i-1], (ll)p[i].s);
for(int i = n; i >= 1; i--)
suf[i] = max(suf[i+1], (ll)2 * p[i].s + p[i].a);
for(int i = 1; i <= n; i++)
printf("%lld\n", max(sum[i] + 2 * pre[i], sum[i-1] + suf[i]));
//取前 i 个或者舍掉第 i 个换取后缀的最大
return 0;
}