[JXOI2018]守卫

题目

首先如果(i)处的保镖可以监视(j)((j<i)),当且仅当(forall kin(j,i)),满足(frac{h_i-h_j}{i-j}<frac{h_i-h_k}{i-k})

于是我们可以(O(n^2))处理好每对(i,j)是否可以监视

一个非常显然的性质,如果要监视([l,r])这个区间,那么(r)处必须有一个保镖

我们设(dp_{l,r})表示监视([l,r])这个区间最少放置多少个保镖

我们考虑(r)可以监视的一个点(x),那么([x+1,r))的点都不能监视比(x)更靠前的点

感性理解一下就是(x)这个点比较高,使得后面的点看不到前面了

于是我们发现固定了右端点,那么这个点不能监视到的一些区间([l_i,r_i])是相互独立的,想要监视([l_i,r_i])就必须在(r_i)或者(r_i+1)处设置保镖,于是(dp_{l,r}=1+sum min(dp_{l_i,r_i},dp_{l_i,r_i+1}))

这样做是(O(n^3))的,我们考虑枚举右端点,这样就可以在往前面扫的过程中维护那个(sum),从而复杂度降到了(O(n^2))

代码

#include <bits/stdc++.h>
#define re register
#define db double
#define min(a, b) ((a) < (b) ? (a) : (b))
inline int read() {
    char c = getchar();
    int x = 0;
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - 48, c = getchar();
    return x;
}
const int maxn = 5e3 + 3;
int n, h[maxn];
int dp[maxn][maxn];
bool a[maxn][maxn];
int main() {
    n = read();
    for (re int i = 1; i <= n; i++) h[i] = read();
    for (re int i = 2; i <= n; i++) {
        db now = 1e20;
        for (re int j = i - 1; j; --j)
            if ((db)(h[i] - h[j]) / (i - j) < now)
                now = (db)(h[i] - h[j]) / (i - j), a[j][i] = 1;
    }
    dp[1][1] = 1;
    dp[2][2] = 1;
    dp[1][2] = 1;
    for (re int i = 3; i <= n; i++) {
        dp[i][i] = 1;
        int sum = 0, p = i;
        for (re int j = i - 1; j; --j)
            if (a[j][i]) {
                if (!a[j + 1][i])
                    sum += min(dp[j + 1][p - 1], dp[j + 1][p]);
                dp[j][i] = 1 + sum;
                p = j;
            } else
                dp[j][i] = min(dp[j][p - 1], dp[j][p]) + sum + 1;
    }
    int ans = 0;
    for (re int i = 1; i <= n; i++)
        for (re int j = i; j; --j) ans ^= dp[j][i];
    printf("%d
", ans);
    return 0;
}

原文地址:https://www.cnblogs.com/asuldb/p/11295280.html