题解 CF1476F 【Lanterns】

RiverHamster · 2021-02-01 21:49:22 · 题解

设计 DP 状态 f_i 表示前 i 盏灯可以点亮的最长前缀，初值为 f_0 = f_1 = 0。

考虑如下几种转移：

• 前 i - 1 盏灯无法覆盖 i，直接忽略掉第 i 盏灯，即 f_i \gets f_{i-1}；

• 前 i - 1 盏灯可以覆盖 i，第 i 盏灯指向右边，即 f_i \gets \max(f_{i-1}, i + p_i) 其中 f_{i-1} \ge i。

• 第 i 盏灯指向左边，和之前的一个前缀的灯点亮的前缀拼成一个更大的前缀，中间的全部指向右边。即找到最小的非负整数 t，满足 f_t \ge i - p_i - 1，就有转移 f_i \gets \max\{i - 1, t + 1 + p_{t+1}, \dots,i - 1 + p_{i-1}\}。

  二分出 t，用 RMQ 维护 i + p_i 区间最大即可。

最后记录转移位置即可输出方案。复杂度 \mathcal O(n \log n)，当然精细实现可以 \mathcal O(n)。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <vector>
using namespace std;

#define LOG(f...) fprintf(stderr, f)

using ll = long long;

template<class T> void read(T &x){
  char ch; x = 0;
  int f = 1;
  while (isspace(ch = getchar()));
  if (ch == '-') ch = getchar(), f = -1;
  do x = x * 10 + ch - '0'; while(isdigit(ch = getchar()));
  x *= f;
}
template<class T, class ...A> void read(T &x, A&... args) { read(x); read(args...); }

const int N = 300005;
int p[N], f[N], from[N];
int n;
int st[20][N];
char res[N];

void buildST() {
  for (int i = 1; i <= n; ++i)
    st[0][i] = i + p[i];
  for (int i = 1, li = __lg(n); i <= li; ++i)
    for (int j = 1; j <= n - (1 << i) + 1; ++j)
      st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
}
int range_max(int l, int r) {
  if (l > r) return 0;
  int k = __lg(r - l + 1);
  return max(st[k][l], st[k][r - (1 << k) + 1]);
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
  int T;
  read(T);
  while (T--) {
    read(n);
    for (int i = 1; i <= n; ++i) read(p[i]);
    buildST();
    fill(f + 1, f + 1 + n, 0);
    from[1] = 1;
    for (int i = 2; i <= n; ++i) {
      if (!p[i]) { f[i] = f[i - 1]; from[i] = i; continue; }
      int t = lower_bound(f, f + i, i - p[i] - 1) - f;
      from[i] = t;
      if (t == i) f[i] = f[i - 1];
      else {
        f[i] = max(i - 1, range_max(t + 1, i - 1));
        if (f[i - 1] > f[i]) f[i] = f[i - 1], from[i] = i;
        if (f[i - 1] >= i && i + p[i] > f[i]) {
          f[i] = i + p[i];
          from[i] = i;
        }
      }
    }

    if (f[n] < n) puts("NO");
    else {
      puts("YES");
      int cur = n;
      while (cur) {
        if (from[cur] == cur) res[cur] = 'R', --cur;
        else {
          res[cur] = 'L';
          fill(res + from[cur] + 1, res + cur, 'R');
          cur = from[cur];
        }
      }
      res[n + 1] = 0; puts(res + 1);
    }
  }
  return 0;
}