嘿嘿嘿我已经懒成这样了……
简单翻译:
Vasya有n个题目可选,每道题难度为d[i],买这道题要花的钱为c[i]。他最后一定要选连续的一堆题买过来(也可以不选),即一个区间。然后每道题目他能卖a块钱(注意这是个定值,每道都是a元),这样他赚了一些钱吧,还没完,还要扣点钱,即gap,注意这个gap,之后我们要多次提到。gap的具体定义见题目中的数学公式,口述会凌乱。
输入描述:
第一行输入n,a,代表题目数量和每道题要卖的价格。接下来n行输入每道题的难度d[i]和成本价c[i]。输入保证难度d[i]是递增的。
输出描述:
输出一个整数,代表Vasya最多能赚多少钱。
样例:
Input 1:
5 10
1 15
5 3
6 11
7 2
11 22
Output 1:
13
Input 2:
3 5
1 8
2 19
3 11
Output 2:
0
题目简析:
0.以下啰嗦预警。入门新手及易睡人员请直接跳转到9.
1.答案要取连续的区间疯狂暗示线段树。
2.外层枚举r,内层枚举l显然过于暴力。
3.考虑内层的优化。dp[i]:以第i位为结尾的答案(长度大于1的)。dp[i] = max(第一种情况,第二种情况)。解释一下,首先我们可以做到求出i前面gap[j] > gap[i],j < i最大的j的位置pos,然后其中第一种情况为:自力更生,区间pos~i内gap[i]是最大的。这种情况可以使用线段树logn得到区间内最大右子段和;其中第二种情况为:寄人篱下,区间从pos前的某一位一直到i,即最大的gap不是gap[i]。这种直接dp转移,dp[pos] + sum[pos + 1 ~ i]即可。
4.怎样不暴力枚举巧妙得到pos?这里提供单调栈的方式,每个元素都只进出一次,复杂度完全可以承受。
5.注意一些细节操作,比如最大右子段可能只有一位的长度,所以代码中用pos~i-1的右子段加上了第i位的值以保证长度大于1.
6.为啥非得dp长度大于1的?因为等于1的跟gap没关系了,没法这么搞,且长度为1的……完全可以一开始读入的时候就更新掉。
7.请结合代码细细体会。这好像是我第一次在这里扔我的线段树板子(虽然由于题目原因,是残缺的)。
8.另一种非dp做法:
因为答案的maxgap肯定只在n-1个里面选,所以枚举这n-1个gap,然后区间咋选呢,就是:对于这个gap[i],我们可以做到求出两个数组l[i]和r[i],其实和上一个做法很像,l[i]就是gap[i]还能做“土皇帝”向左走得最远的位置,再往左走他就不是最大的了;同理r[i]是向右走的最远。这样只要用线段树查询l[i]到r[i]的最大连续子段和即可。注意有可能i不在这个连续子段和里,但是没关系,这样算出来的值比答案更劣因为减去gap减多了,而我们一会儿就会枚举到真正的答案并更新了。啊对了,l和r数组是在枚举之前用单调栈预处理的,跟dp的那个差不太多……有兴趣的自己写一写,没写出来可以搜一搜或者后台找我。
9.一点闲话(您硬着头皮读(or 滑动)到这里的奖励)。
9.1 其实举例和画图远远比口胡抽象概念更直观、易于理解,也是我一直提倡、却鲜有老师来做的事情。如果AlphaWA很闲、至少不忙的话,或者有一定的盈利的话(删去),当然会身体力行地实践这个事;但是……以前的文章其实尝试过,一弄可能大半天就没了,每次都如此也是很伤,尤其以前的题还是简单题,现在的已经不是三言两语一两张图能说完的了。
9.2 所以只能麻烦大家配合着口胡(口胡必定意识流)啃一啃代码,我感觉我码风和代码逻辑安排都还好吧,最起码不是毒瘤……然后希望读者们可以真的去做一做放出来的题目(才能看明白口胡解析是在说啥),就一道也不多,网上题解也满天飞。
9.3(对我来说的)重点??? 然后日更的事情,公众号可能不行。找题、翻译、写题解、加注释、排版、回复后台消息、回复某些上古题目的留言……一套下来也是费很多时间,非盈利的是做不来的,尤其目前主要是dansen和AlphaWA两个人在负责这些,之前(or现在)也有mxg、天马、紫芝、逆风、Pimithe等等一些小伙伴投稿帮忙(其实很多篇呢!表达感谢!)。有日更兴趣的读者可以到本菜鸡AlphaWA的博客园逛,不忙的时候是按当天情绪日若干更。热烈欢迎比赛写题互相促进的朋友来交流。
最后给大家带来的不便,希望谅解,就酱~
回归课堂。非dp代码咕咕咕,dp代码主要部分:
const int maxn = 3e5 + 5;
int n;
ll a, d[maxn], c[maxn], dp[maxn], ans;
class SegmentTree {
public:
#define ls(p) p << 1
#define rs(p) p << 1 | 1
struct Node {
int l, r;
ll rs, sum;
}t[maxn << 2];
void Push_Up(int p) {
t[p].sum = t[ls(p)].sum + t[rs(p)].sum;
t[p].rs = max(t[rs(p)].rs, t[ls(p)].rs + t[rs(p)].sum);
}
void Build(int l, int r, int p) {
t[p].l = l, t[p].r = r;
if (l == r) {
t[p].rs = t[p].sum = c[l];
return;
}
int mid = (l + r) >> 1;
Build(l, mid, ls(p));
Build(mid + 1, r, rs(p));
Push_Up(p);
}
friend Node operator + (const Node x, const Node y) {
return (Node){x.l, y.r, max(y.rs, x.rs + y.sum), x.sum + y.sum};
}
Node Query(int l, int r, int p) {
if (l <= t[p].l && t[p].r <= r) {
return t[p];
}
int mid = (t[p].l + t[p].r) >> 1;
if (r <= mid) return Query(l, r, ls(p));
if (mid < l) return Query(l, r, rs(p));
return Query(l, r, ls(p)) + Query(l, r, rs(p));
}
}T;
int main() {
read(n), read(a);
rep(i, 1, n) {
read(d[i]);
read(c[i]);
c[i] = a - c[i];
ans = max(ans, c[i]);
}
T.Build(1, n, 1);
rep(i, 1, n) c[i] += c[i - 1];
stack<pair<ll, int>> stk;
rep(i, 2, n) {
int pos;
while (!stk.empty() && stk.top().first < d[i] - d[i - 1]) {
stk.pop();
}
if (stk.empty()) pos = 1;
else pos = stk.top().second;
stk.push(make_pair(d[i] - d[i - 1], i));
dp[i] = T.Query(pos, i - 1, 1).rs + c[i] - c[i - 1] - (d[i] - d[i - 1]) * (d[i] - d[i - 1]);
if (pos != 1) dp[i] = max(dp[i], dp[pos] + c[i] - c[pos]);
ans = max(dp[i], ans);
}
writeln(ans);
return 0;
}