Codeforces 1107G Vasya and Maximum Profit
题目链接
http://codeforces.com/contest/1107/problem/G
题目大意
有 $n$ 个题，每选择一道题你会获得 $a$ 的收益，同时需要花费 $c_i$ 才能获得第 $i$ 道题。每道题的难度为 $d_i$ ，令 $gap(l, r) = \max\limits_{l \le i < r} (d_{i + 1} – d_i)^2$ 。你需要选择一段连续的题目，使得这些题目的净收益减去 $gap(l, r)$ 最大。
题目分析
由于是连续的一段题目，所以可以考虑使用分治的思想，考虑一个区间分成两个子区间，则答案可能出现在两个子区间中，也可能横跨两个区间。在两个子区间的很好解决，递归求解即可，如果长度为 $1$ 的话就直接返回 $a – c_l$ 即可。
那么考虑横跨两个区间的情况，显然可知，起点一样的 $gap$ 在长度增长的同时一定也是递增的，因此可以分成两种情况讨论，左区间的 $gap$ 大于或者小于右区间的 $gap$，简单合并即可。
官方题解还给出了线段树的做法，将所有相邻点的 $gap$ 从小到大排序，依次将它们添加至线段树中，维护最大连续子序列即可，想法也十分的巧妙。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 3e5 + 5;
long long n, m;
long long c[maxn];
long long d[maxn];
long long ans = 0;
int read(){
int x;
scanf("%d", &x);
return x;
}
long long sqr(long long x){
return x * x;
}
int dfs(int l, int r){
int mid = (l + r) / 2;
int i, j;
if(l == r){
ans = max(ans, m - c[l]);
}else{
dfs(l, mid);
dfs(mid + 1, r);
vector <long long> a[2];
vector <long long> b[2];
a[0].resize(mid - l + 1);
a[1].resize(mid - l + 1);
b[0].resize(r - mid);
b[1].resize(r - mid);
a[0][0] = m - c[mid];
a[1][0] = d[mid + 1] - d[mid];
for(i=1;i<mid-l+1;i++){
a[0][i] = a[0][i - 1] + m - c[mid - i];
a[1][i] = max(a[1][i - 1], d[mid - i + 1] - d[mid - i]);
}
b[0][0] = m - c[mid + 1];
b[1][0] = d[mid + 1] - d[mid];
for(i=1;i<r-mid;i++){
b[0][i] = b[0][i - 1] + m - c[mid + i + 1];
b[1][i] = max(b[1][i - 1], d[mid + i + 1] - d[mid + i]);
}
i = 0, j = 0;
long long maxa = a[0][0], maxb = b[0][0];
while(i < mid - l + 1){
maxa = max(maxa, a[0][i]);
while(j + 1 < r - mid and b[1][j + 1] <= a[1][i]){
j++;
maxb = max(maxb, b[0][j]);
}
ans = max(ans, maxa + maxb - sqr(a[1][i]));
i++;
}
i = 0, j = 0;
maxa = a[0][0], maxb = b[0][0];
while(j < r - mid){
maxb = max(maxb, b[0][j]);
while(i + 1 < mid - l + 1 and a[1][i + 1] <= b[1][j]){
i++;
maxa = max(maxa, a[0][i]);
}
ans = max(ans, maxa + maxb - sqr(b[1][j]));
j++;
}
}
return 0;
}
int main(){
int i, j;
n = read();
m = read();
for(i=1;i<=n;i++){
d[i] = read();
c[i] = read();
}
dfs(1, n);
printf("%lld\n", ans);
return 0;
}