LOJ6502. 「雅礼集训 2018 Day4」Divide（构造＋dp）

题目链接

题解

中间一档部分分提示我们将所有的 \(w_i\) 排序。

考虑如果我们能构造出这样一个 \(w_i\) 的序列，使得该序列满足：对于任意的 \(i(1 \leq i \leq n)\)，所有的 \(j(1 \leq j < i)\) 都满足 \(w_i + w_j \geq m\) 或者所有的 \(j(1 \leq j < i)\) 都满足 \(w_i + w_j < m\)，那么我们就可以使用动态规划求解。

具体地，设 \(f_{i, j}\) 表示处理到了 \(w_i\)，且 \(A\) 队中已有 \(j\) 个元素能得到的最大贡献值。若 \(w_i\) 满足对于任意 \(j(1 \leq j < i)\) 有 \(w_i + w_j \geq m\)，那么考虑将 \(w_i\) 放入 \(A\) 队，则 \(w_i\) 与前面所有放入 \(B\) 队的 \(i - j\) 个元素都能配合默契，因此有 \(f_{i, j} = f_{i - 1, j - 1} + i - j\)；考虑放入 \(B\) 队，则 \(w_i\) 与前面所有放入 \(A\) 队中的 \(j\) 个元素都能配合默契，因此有 \(f_{i, j} = f_{i - 1, j} + j\)，最终答案在两者间取 \(\rm max\)。若 \(w_i\) 满足对于任意 \(j(1 \leq j < i)\) 有 \(w_i + w_j < m\)，由于无论放入 \(A\) 队还是 \(B\) 队都不能造成贡献，因此转移为 \(f_{i, j} = {\rm max}\{f_{i - 1, j - 1}, f_{i - 1, j}\}\)。求方案数在转移 \(f\) 时一起统计即可。

现在的问题是如何构造这个序列。

我们先将 \(w\) 从小到大排序，发现若 \(w_1 + w_n \geq m\)，那么对于任意的 \(j(1 \leq j < n)\) 均满足 \(w_j + w_n \geq m\)；若 \(w_1 + w_n < m\)，那么对于任意的 \(j(1 < j \leq n)\) 均满足 \(w_1 + w_j < m\)，但依然有可能存在 \(j(1 \leq j < n)\) 满足 \(w_j + w_n \geq m\)。

因此，我们可以思考如下算法：对于按从小到大排序后得到的区间 \([l, r]\)，若满足 \(w_l + w_r \geq m\)，那么弹出 \(w_r\)，处理区间 \([l, r - 1]\)，否则弹出 \(w_l\)，处理区间 \([l + 1, r]\)。每次我们将弹出的数放到一个新的数组 \(p\) 的最左端，那么可以证明，得到的 \(p\) 数组就能够满足我们所需要的性质。

我们求出数组 \(p\) 后，就能够通过 dp 在 \(O(n^2)\) 的时间内解决此题了。

代码

#include<bits/stdc++.h>

using namespace std;

#define X first

#define Y second

#define mp make_pair

#define pb push_back

#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;

typedef long double ld;

typedef unsigned int uint;

typedef pair<int, int> pii;

typedef unsigned long long ull;

template<typename T> inline void read(T& x) {

  char c = getchar();

  bool f = false;

  for (x = 0; !isdigit(c); c = getchar()) {

    if (c == '-') {

      f = true;

    }

  }

  for (; isdigit(c); c = getchar()) {

    x = x * 10 + c - '0';

  }

  if (f) {

    x = -x;

  }

}

template<typename T> inline bool checkMax(T& a, const T& b) {

  return a < b ? a = b, true : false;

}

template<typename T> inline bool checkMin(T& a, const T& b) {

  return a > b ? a = b, true : false;

}

const int N = 2e3 + 10, mod = 1e9 + 7;

inline void add(int& x, int y) {

  x = (x + y) % mod;

}

int n, m, a[N], all[N], f[N][N], g[N][N];

int main() {

  read(n), read(m);

  for (register int i = 1; i <= n; ++i) {

    read(a[i]);

  }

  sort(a + 1, a + 1 + n);

  int l = 1, r = n;

  for (register int i = n; i; --i) {

    if (a[l] + a[r] >= m) {

      all[i] = 1, --r;

    } else {

      all[i] = 0, ++l;

    }

  }

  int ans = 0;

  g[0][0] = 1;

  for (register int i = 1; i <= n; ++i) {

    for (register int j = 0; j <= i; ++j) {

      if (j ^ i) {

        int v = f[i - 1][j] + (all[i] ? j : 0);

        if (v > f[i][j]) {

          f[i][j] = v, g[i][j] = g[i - 1][j];

        } else if (v == f[i][j]) {

          add(g[i][j], g[i - 1][j]);

        }

      } if (j) {

        int v = f[i - 1][j - 1] + (all[i] ? i - j : 0);

        if (v > f[i][j]) {

          f[i][j] = v, g[i][j] = g[i - 1][j - 1];

        } else if (v == f[i][j]) {

          add(g[i][j], g[i - 1][j - 1]);

        }

      }

      checkMax(ans, f[i][j]);

    }

  }

  int res = 0;

  for (register int i = 0; i <= n; ++i) {

    if (f[n][i] == ans) {

      add(res, g[n][i]);

    }

  }

  printf("%d %d\n", ans, res);

  return 0;

}

巴特西

LOJ6502. 「雅礼集训 2018 Day4」Divide（构造＋dp）

题目链接

题解

代码

最新文章

热门文章