\(\mathscr{Description}\)

  Link.

  给定 \(n\) 盏灯, 你可以选择让第 \(i\) 盏照亮 \([i-p_i,i)\) 或者 \((i,i+p_i]\), 构造方案覆盖 \([1,n]\) 内的整点, 或声明无解.

  多测, \(\sum n\le3\times10^5\).

\(\mathscr{Solution}\)

  某模拟赛后得知这是典题, 那兔是脱离时代了. 加之最近好像更博客比较咕 (你以为是在写 Tower? 当然不是! 就是咕, 咕咕咕呱), 所以写写单题题解吧.

  这看上去是一个判定性问题, 但 01 状态显然损失了信息量. 所以无论是区间 DP 还是什么序列 DP, 我们设计 DP 状态的思路都是 “最大/最小化某个东西, 尽可能让子问题有解”.

  比如我们有这么一个设计: 令 \(f(i)\) 表示考虑了灯 \([1,i]\), 最多能完全照亮 \([1,f(i)]\) 内的整点. 诸如此类的状态似乎都有转移后效性, 这就是本题的难点.

  去掉后效性? 贪心地整体决策! 对于上面这个状态, 如果 \(i\) 选择向前覆盖, 而若覆盖到一个已有 \(f(j)\ge j\) 的 \(j\), 我们自然让 \((j,i)\) 内的灯全部向右照. 若此时 \(f(j)\) 的实际决策还能增大 \(f(i)\) 的理想值 … 那 \(i\) 摆烂得了, 不需要我们来考虑转移.

  意识流地讨论之后, 我们来具体分析转移.

• \(i\) 摆烂. \(f(i)\overset{\max}{\longleftarrow}f(i-1)\);
• \(i\) 往右照, 要求 \(i\) 自己被照到, 不然相当于 \(i\) 摆烂. \(f(i)\overset{\max}{\longleftarrow}\max\{f(i-1),i+p_i\}\), 其中 \(f(i-1)\ge i\).
• \(i\) 往右照, 这是刚刚糊过的难点. \(f(i)\overset{\max}{\longleftarrow}\max\{\{k+p_k\mid k\in(j,i)\}\cup\{i-1\}\}\), 其中 \(j\) 满足 \(f(j)\ge i-p_i-1\).

  (这里其实我觉得没必要分自然段, 但是我怕有人觉得我忘记分段了所以还是分一下段. 欸你写题解屁话真的多.) 需要优化一下第三种转移, 显然最小的 \(j\) 将带来最优质转移. std::lower_bound 出 \(j\), 挂上 BIT 在线求 RMQ 即可. 复杂度 \(\mathcal O(n\log n)\). 听闻 “精细实现” 可以 \(\mathcal O(n)\) awa!

\(\mathscr{Code}\)

/*+Rainybunny+*/

#include <bits/stdc++.h>

#define rep(i, l, r) for (int i = l, rep##i = r; i <= rep##i; ++i)
#define per(i, r, l) for (int i = r, per##i = l; i >= per##i; --i)

typedef std::pair<int, int> PII;
#define fi first
#define se second

inline char fgc() {
    static char buf[1 << 17], *p = buf, *q = buf;
    return p == q && (q = buf + fread(p = buf, 1, 1 << 17, stdin), p == q) ?
      EOF : *p++;
}

template <typename Tp = int>
inline Tp rint() {
    Tp x = 0, s = fgc(), f = 1;
    for (; s < '0' || '9' < s; s = fgc()) f = s == '-' ? -f : f;
    for (; '0' <= s && s <= '9'; s = fgc()) x = x * 10 + (s ^ '0');
    return x * f;
}

template <typename Tp>
inline void wint(Tp x) {
    if (x < 0) putchar('-'), x = -x;
    if (9 < x) wint(x / 10);
    putchar(x % 10 ^ '0');
}

const int MAXN = 3e5;
int n, p[MAXN + 5], f[MAXN + 5], pre[MAXN + 5];
char ans[MAXN + 5];

struct BIT {
    PII val[MAXN + 5];
    inline void modify(int x, const PII& k) {
        for (; x <= n; x += x & -x) val[x] = std::max(val[x], k);
    }
    inline PII query(int x) const {
        PII ret(0, 0);
        for (; x; x ^= x & -x) ret = std::max(ret, val[x]);
        return ret;
    }
} bit;

int main() {
    for (int T = rint(); T--;) {
        n = rint();
        rep (i, 1, n) p[i] = rint();

        memset(bit.val + 1, 0, sizeof(bit.val[1]) * n);
        bit.modify(n, { 1 + p[1], 1 });
        rep (i, 2, n) {
            f[i] = f[i - 1], pre[i] = -1;
            if (f[i - 1] >= i) f[i] = std::max(f[i - 1], i + p[i]);
            int idx = std::lower_bound(f, f + i, i - p[i] - 1) - f;
            PII t = bit.query(n - idx);
            if (idx < i && f[i] < std::max(i - 1, t.fi)) {
                f[i] = std::max(i - 1, t.fi), pre[i] = idx;
            }
            bit.modify(n - i + 1, { i + p[i], i });
            // printf("f(%d)=%d\n", i, f[i]);
        }

        if (f[n] < n) puts("NO");
        else {
            puts("YES"), ans[n + 1] = '\0';
            for (int p = n; p;) {
                // assert(~pre[p] && f[p] >= p);
                if (!~pre[p]) ans[p] = 'R', --p;
                else {
                    int t = pre[p]; ans[p] = 'L';
                    while (--p > t) ans[p] = 'R';
                }
            }
            puts(ans + 1);
        }
    }
    return 0;
}

原文地址：http://www.cnblogs.com/rainybunny/p/16864050.html