BZOJ2216: [Poi2011]Lightning Conductor(DP 决策单调性)

题意

题目链接

Sol

很nice的决策单调性题目

首先把给出的式子移项,我们要求的$P_i = max(a_j + \sqrt{|i - j|}) - a_i$。

按套路把绝对值拆掉,$p_i = max(max_{j = 1}^i (a_j = \sqrt{i - j}), max_{j = i + 1}^n (a_j + \sqrt{j - i})) - a_i$

对于后面的一段,我们把序列翻转之后和前一段是等价的。

也就是说,我们现在只需要找到$P_i = max_{j = 1}^i (a_j + \sqrt{i - j})$

考虑到式子中只有一个max函数,那这玩意儿应该是有决策单调性的

直接设$f_j = a_j + \sqrt{i - j}, i \geqslant j$,其中$i$是自变量

观察这个函数,应该是一个在$[j, INF]$内有定义,过点$(j, a[j])$的函数,且增速与函数$g_i = \sqrt{i}$相同

我们需要做的,就是对每个$i$,找到最大的$f_j$

考虑到$g_i$增长速度会越来越慢,所以一个函数增长到一定程度后可能会被另一个函数取代

直接用单调队列维护,设$K_{i, j}$表示$f_i, f_j$的交点,$h, t$分别表示队首/尾,

当新加入一个元素$i$的时候,显然,若$K_{t -1, t} > K_{t - 1, i}$,那么$t$这个函数是没用的、

当$K_{h, h+1} < i$的时候,弹出队首

就是最后输出答案的时候有点“卡精度”,真恶心

经验:

以后看到$f_i = max(f_j) + g$的式子一定要往单调性上想,如果单调性不是很显然的话可以用换元法设函数找单调性

另外绝对值拆开算一般会好算一些

#include<bits/stdc++.h>
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, a[MAXN], q[MAXN], Cro[MAXN];
double P[MAXN], sqr[MAXN];
double calc(int j, int i) {
    return a[j] + sqr[i - j];
}
int K(int x, int y) {
    int l = max(x, y), r = N, ans = N + 1;
    while(l <= r) {
        int mid = l + r >> 1;
        if(calc(x, mid) >= calc(y, mid)) l = mid + 1;
        else r = mid - 1, ans = mid;
    }
    return ans;
}
void solve() {
    int h = 1, t = 0;
    for(int i = 1; i <= N; i++) {
        while(h < t && K(q[t - 1], q[t]) >= K(q[t], i)) t--;
        q[++t] = i;
        while(h < t && K(q[h], q[h + 1]) <= i) h++;
        P[i] = max(P[i], calc(q[h], i));
    }
}
main() {
    N = read();
    for(int i = 1; i <= N; i++) a[i] = read(), sqr[i] = sqrt(i);
    solve();
    reverse(a + 1, a + N + 1);
    reverse(P + 1, P + N + 1);
    solve();
    for(int i = N; i >= 1; i--)
        printf("%d\n", max(0, (int)ceil(P[i]) - a[i]));
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PPV课数据科学社区

数据挖掘知识脉络与资源整理(十)–箱线图

? ? 箱线图的简介 箱形图(Box-plot)又称为盒须图、盒式图或箱线图,是一种用作显示一组数据分散情况资料的统计图。因形状如箱子而得名。在各种领域也经常...

34680
来自专栏算法修养

POJ 1964&HDU 1505&HOJ 1644 City Game(最大0,1子矩阵和总结)

最大01子矩阵和,就是一个矩阵的元素不是0就是1,然后求最大的子矩阵,子矩阵里的元素都是相同的。 这个题目,三个oj有不同的要求,hoj的要求是5s,...

35340
来自专栏ACM算法日常

当七夕遇上算法竞赛

  七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。于是TYVJ今年举办了一次线下七夕祭。Vani同学今年成功邀请到了cl同学陪他来共度七夕,于是他们决定去T...

15520
来自专栏懒人开发

(5.5)James Stewart Calculus 5th Edition:The Substitution Rule

注意: 这里 自变量改变,对应范围也会改变 不定积分的上下限,由 [a, b] 变为了 [g(a), g(b)]

11730
来自专栏javascript趣味编程

5.2.1 二维导热算例-热导的概念

材料类,描述材料的参数,如密度、比热和初始温度等,这里特别给出了凝固潜热;这里要注意Math.pow(2,0)的意义,读者自己琢磨,用于判断相邻控制体的...

11600
来自专栏数据结构与算法

#15. 钻石

钻石 diamond.in/.out/.cpp 【问题描述】 你有 n 个 “量子态” 的盒子,每个盒子里可能是一些钱也可能是一个钻 石。 现在你知道如果打开第...

29660
来自专栏章鱼的慢慢技术路

Go指南练习_循环与函数

24720
来自专栏常用编程思想与算法

常用编程思想与算法

本文是在阅读Aditya Bhargava先生算法图解一书所做的总结,文中部分代码引用了原文的代码,在此感谢Aditya Bhargava先生所作出的这么简单的...

22410
来自专栏深度学习那些事儿

pytorch新手需要注意的隐晦操作Tensor,max,gather

先看官方的介绍: 如果input是一个n维的tensor,size为 (x0,x1…,xi−1,xi,xi+1,…,xn−1),dim为i,然后index必须...

1.6K80
来自专栏PPV课数据科学社区

【学习】笨办法学R编程(四)

随着教程推进,基本的语法都接触得差不多了。当要解决某个具体问题时,只需要考虑用什么样的算法来整合运用这些函数和表达式。今天来解决Project ...

28940

扫码关注云+社区

领取腾讯云代金券