QOJ #7645. Shoes 题解

Description

尼基塔计划度假时，决定好好享受一下并为自己买一双新鞋。为此，他研究了位于他酒店所在街道上的各家商店，并选择了 $n$ 双鞋来试穿。尼基塔知道，每双鞋需要 $k$ 秒钟来试穿，并打算每天安排 $T$ 秒钟的时间来访问商店。街道是一个坐标轴，移动速度为每秒一单位，酒店位于原点，每次访问商店都必须从酒店出发并返回。求尼基塔试穿完所有他感兴趣的鞋子所需要的最少假期天数。

$n\leq 10^4$。

Solution

显然一个方案的时间只与最左和最右端点有关，所以我们可以把每次行走抽象成灾区间 $[l,r]$ 可以选 $c$ 个买。

然后有个观察是我们选择的区间只会互相包含和不交，否则设 $c_1$ 和 $c_2$ 分别表示两个区间可以买的个数，那么一定可以调整成前 $c_1$ 个和后 $c_2$ 个放一起。

考虑区间 dp。

设 $f_{l,r}$ 表示只考虑 $[l,r]$ 的子区间，将 $[l,r]$ 消掉的最小天数。

首先如果不操作 $[l,r]$ 这整个区间，那么一定存在一个最优方案使得 $[l,p]$ 或者 $[p,r]$ 可以买的个数等于区间长度，这个 $O(n)$ 预处理出来最远的端点可以做到 $O(1)$ 转移。

如果操作 $[l,r]$，设 $c$ 表示 $[l,r]$ 的权值。那么剩下的 $len-c$ 个没有被这次删掉的点一定构成一段区间，否则同样能够调整。这部分转移形如：$f_{l,r}\leftarrow f_{i,i+len-c-1}+1$。

按照 $r$ 从小到大转移的话这就是查询后缀最小值，对于每个长度 $k$，维护 $nxt_{k,i}$ 表示 $i$ 右边第一个权值小于 $f_{i,i+k-1}$ 的位置，这样查询时可以并查集维护。每次加入新区间只需要判断所有没找到 $nxt$ 的能否更新即可。

时间复杂度：$O(n^2\log n)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

using i64 = int64_t;

const int kMaxN = 1e4 + 5;

int n; i64 k, t, a[kMaxN];
int f[kMaxN][kMaxN], fa[kMaxN][kMaxN], pre[kMaxN], nxt[kMaxN];
std::vector<int> vec[kMaxN];

inline void chkmax(int &x, int y) { x = (x > y ? x : y); }
inline void chkmin(int &x, int y) { x = (x < y ? x : y); }

int calc(int x, int y) {
  i64 s = llabs(a[x]) + llabs(a[y]) + llabs(a[y] - a[x]);
  if (s <= t) return std::min<i64>((t - s) / k, n);
  else return 0;
}

int find(int *fa, int x) { return x == fa[x] ? x : fa[x] = find(fa, fa[x]); }

void dickdreamer() {
  std::cin >> n >> k >> t;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  std::sort(a + 1, a + 1 + n);
  for (int i = 1; i <= n; ++i) {
    pre[i] = i + 1;
    for (int j = i; j; --j) {
      if (calc(j, i) >= i - j + 1) pre[i] = j;
      else break;
    }
    nxt[i] = i - 1;
    for (int j = i; j <= n; ++j) {
      if (calc(i, j) >= j - i + 1) nxt[i] = j;
      else break;
    }
  }
  for (int len = 1; len <= n; ++len) {
    for (int i = 1; i <= n - len + 1; ++i)
      fa[len][i] = i;
  }
  memset(f, 0x3f, sizeof(f));
  for (int r = 1; r <= n; ++r) {
    for (int l = r; l; --l) {
      int c = calc(l, r);
      if (c >= r - l + 1) {
        f[l][r] = 1;
      } else {
        if (l == r) continue;
        int len = r - l + 1 - c;
        f[l][r] = std::min(f[nxt[l] + 1][r] + 1, f[l][pre[r] - 1] + 1);
        int pos = find(fa[len], l);
        chkmin(f[l][r], f[pos][pos + len - 1] + 1);
        // for (int i = l; i <= r - len + 1; ++i) chkmin(f[l][r], f[i][i + len - 1] + 1);
      }
      int len = r - l + 1;
      for (; vec[len].size(); vec[len].pop_back()) {
        int x = vec[len].back();
        if (f[x][x + len - 1] < f[l][r]) break;
        fa[len][x] = l;
      }
      vec[len].emplace_back(l);
    }
  }
  std::cout << f[1][n] << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}