题解：CF2207C Where's My Water?

· · 题解

数据范围允许做 O(n^2) 甚至是 O(n^2 \log n)，那就直接枚举上两个排水孔，发现如果直接求的话重叠部分不好做，那就看看能不能不算重叠的。

发现一个性质，若在 (i,a_i+1) 和 (j,a_j+1) 放置排水口，其中 j - i \ge 2，那么找到索引 k，i < k < j，满足 a_k 是所有满足条件的索引当中最大的，那么对于这个位置的右边，i 能吸到的水 j 一定也能吸到，那在右边的就让 j 吸，反之左边的就让 i 吸，设 f_{i,j} 为吸水口在 i，让他去吸 \left[ 1,j\right] 的水能吸多少，g_{i,j} 为吸水口在 i，让他去吸 \left[ j,n\right] 的水能吸多少，这两个都能很简单的用递推得到，关于最大值的位置，线段树解决即可。

这样交上去就 Wrong answer on pretest 2 了，观察 hack：

3 4
3 1 2

如果放一个在中间，可以全部吸走，发现代码中 i,j 都取不到 2，特判即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool Begin;
int n, h, a[1000005], f[2005][2005], g[2005][2005];
pair<int, int> w[4000005]; // first 是最大值，second 是位置
void pushup(int u){
    w[u] = max(w[u << 1], w[u << 1 | 1]);
    if(w[u << 1].first > w[u << 1 | 1].first) w[u] = w[u << 1];
    else w[u] = w[u << 1 | 1];
}
void build(int u, int l, int r){
    if(l == r){
        w[u] = {a[l], l};
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
pair<int, int> query(int u, int l, int r, int L, int R){
    if(L <= l && r <= R){
        return w[u];
    }
    else if(!(r < L || R < l)){
        int mid = (l + r) >> 1;
        pair<int, int> x = query(u << 1, l, mid, L, R), y = query(u << 1 | 1, mid + 1, r, L, R);
        if(x.first > y.first) return x;
        return y;
    }
    return {0, 0};
}
void solve(){
    cin >> n >> h;
    int ans = 0;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
    }
    build(1, 1, n);
    if(n == 1){
        cout << h - a[1] << "\n";
        return;
    }
    else if(n == 2){
        cout << 2 * h - a[1] - a[2] << "\n";
        return;
    }
    for(int i = 1; i <= n; i ++){
        int maxn = a[i]; f[i][i] = 0;
        for(int j = i; j >= 1; j --){
            maxn = max(maxn, a[j]);
            f[i][i] += h - maxn;
        }
        maxn = a[i]; ans = max(ans, f[i][i]); // 特判
        for(int j = i + 1; j <= n; j ++){
            maxn = max(maxn, a[j]);
            f[i][j] = f[i][j - 1] + h - maxn; ans = max(ans, f[i][j]); // 特判
        }
    }
    for(int i = n; i >= 1; i --){
        int maxn = a[i]; g[i][i] = 0;
        for(int j = i; j <= n; j ++){
            maxn = max(maxn, a[j]);
            g[i][i] += h - maxn;
        }
        maxn = a[i];
        for(int j = i - 1; j >= 1; j --){
            maxn = max(maxn, a[j]);
            g[i][j] = g[i][j + 1] + h - maxn;
        }
    }
    for(int i = 1; i <= n; i ++){
        for(int j = i + 2; j <= n; j ++){
            int maxpos = query(1, 1, n, i + 1, j - 1).second;
            ans = max(ans, f[i][maxpos] + g[j][maxpos + 1]);
        }
    }
    cout << ans << "\n";
}
bool End;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --){
        solve();
    }
    cerr << "\nMemory Limit: " << abs(&End - &Begin) / 1048576 << "MB"; return 0;
}