当前位置: 首页 > 工具软件 > lightning4j > 使用案例 >

[POI2011]Lightning Conductor 决策优化

宋和颂
2023-12-01

题目大意:

给定一个长度为 n n n的序列 { a n } \{a_n\} {an},对于每个 i ∈ [ 1 , n ] i \in [1,n] i[1,n],求出一个最小的非负整数 p p p,是的 ∀ j ∈ [ 1 , n ] \forall j \in [1,n] j[1,n],都有 a j ≤ a i + p − ∣ i − j ∣ a_j \le a_i+p-\sqrt{|i-j|} ajai+pij
1 ≤ n ≤ 5 e 5 , 0 ≤ a i ≤ 1 e 9 1 \le n \le 5e5, 0 \le a_i \le 1e9 1n5e5,0ai1e9

解题思路:

  • 式子可以转换为: a j + ∣ i − j ∣ − a i ≤ p a_j +\sqrt{|i-j|} - a_i \le p aj+ij aip
  • 通过暴力打表可以发现对于每个 p i p_i pi转移的 j i j_i ji都是递增的,所以可以通过决策单调性来优化
  • 而因为 ∣ i − j ∣ \sqrt{|i-j|} ij 的增长速度是逐渐下降的,所以可能存在某个 j 2 > j 1 j_2>j_1 j2>j1,在到某个 i i i之后 a [ j 2 ] + i − j 2 > a [ j 1 ] + i − j 1 a[j_2]+\sqrt{i-j_2} > a[j_1]+\sqrt{i-j_1} a[j2]+ij2 >a[j1]+ij1 (原本是 j 1 j_1 j1 j 2 j_2 j2优秀)
  • 所以对于队列里相邻的点,可以通过二分来找靠后的点什么时候比前者更优,注意这些点也要单调递增的

AC代码:

//因为本题的转移代价是sqrt(i-j)而该函数的增长速度是逐渐下降的,
//所以可能存在某个j2>j1,在到某个i之后a[j2]+sqrt(i-j2) > a[j1]+sqrt(i-j1)(原本是小于的)
#include <bits/stdc++.h>
#define ft first
#define sd second
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define seteps(N) fixed << setprecision(N)
#define endl "\n"
const int maxn = 5e5 + 10;
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
const ll mod = 1e9 + 7;
int n, a[maxn], ans[maxn];
int q[maxn], k[maxn];
int find(int x, int y) {
    int lc = y, rc = n, mc, res = n + 1;
    while (lc <= rc) {
        mc = (lc + rc) >> 1;
        if (a[x] + sqrt(mc - x) <= a[y] + sqrt(mc - y))
            res = mc, rc = mc - 1;
        else
            lc = mc + 1;
    }
    return res;
}
//k[i]放的是队列中第i个点与队列中的第i+1个点,什么时候第i个点的函数曲线会被第i+1个点超过
//队列中的k是单调递增的,如果存在一个i<i+1,但k(i)>k(i+1),意思就是函数曲线第i个点被i+1超过时,i+2早就超过了i+1,则i+1是无用的点
void solve() {
    for (int i = 1, h = 1, t = 0; i <= n; i++) {
        while (h < t && k[t - 1] > find(q[t], i))//保证单调递增,及判断t-1被t超过时,t不能被i超过
            t--;
        k[t] = find(q[t], i); //利用二分查找来得到k
        q[++t] = i;
        while (h < t && k[h] <= i) h++; //队头的k此时已经小过i了,所以弹出
        ans[i] = max(ans[i], (int)(-a[i] + a[q[h]] + ceil(sqrt(i - q[h]))));
    }
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    solve();
    for (int i = 1; i <= n / 2; i++)
        swap(a[i], a[n - i + 1]), swap(ans[i], ans[n - i + 1]);
    solve();
    for (int i = n; i >= 1; i--)
        cout << ans[i] << endl;
}
 类似资料: