[十二省联考2019]皮配 [背包DP]

[十二省联考2019]皮配

题目描述太长是真的难受... 洛谷题解里有个很有意思的简化版题意:豆子有黄色绿色,圆粒皱粒。豆子有重量,每种性状的豆子有重量和上限。同时有一些豆子钦定不能有某种性状。告诉了有多少豆荚,每个豆荚里每个豆子,豆荚里豆子颜色要一样,求方案。

那么就有一种DP的想法:因为两对相对性状,和的数量都是n,令f_{i,j}表示有iC_0jD_0的答案。可以O(nm^2)的做。又因为性状独立,当没有限制的时候可以分开做再乘起来,O(nm)

因为特殊的豆子很少,考虑对没有特殊豆子的豆荚先做一个DP。对有特殊豆子的豆荚做一个高复杂度DP,组合起来。组合的话只需要枚举i,j,并且用前缀和优化。

考虑f_{i,j}的计算。虽然特殊豆子很少,但是它们所在的豆荚大小并没有给定一个小范围。那么必须考虑想办法把它们分开。那么可以考虑把整个豆荚的颜色放在一起DP,但是是圆是皱只对特殊豆子DP。

f复制两份,分别表示两种颜色的方案。枚举豆荚内的特殊豆子,进行更新即可。

#include <bits/stdc++.h>

inline int rd() {
  int a = 1, b = 0; char c = getchar();
  while (!isdigit(c)) a = c == '-' ? 0 : 1, c = getchar();
  while (isdigit(c)) b = b * 10 + c - '0', c = getchar();
  return a ? b : -b;
}

const int N = 2505, P = 998244353;

inline void check(int &x) {
  x -= P, x += x < 0 ? P : 0;
}

int n, c, C0, C1, D0, D1, b[N], s[N], K, hate[N];
int city_s[N], sum_s, city_hate[N];
int f[N], g[N], h[N][N], t1[N][N], t2[N][N];
int ans, ss, sc;

inline int calc_f(int x) {
  int l = std::max(0, sum_s - x - C1), r = C0 - x, ret = 0;
  if (l <= r) {
    ret = f[r];
    if (l != 0)
      check(ret += P - f[l - 1]);
  }
  return ret;
}

inline int calc_g(int x) {
  int l = std::max(0, sum_s - x - D1), r = D0 - x, ret = 0;
  if (l <= r) {
    ret = g[r];
    if (l != 0)
      check(ret += P - g[l - 1]);
  }
  return ret;
}

inline void solve() {

  memset(b, 0, sizeof(b));
  memset(s, 0, sizeof(s));
  memset(hate, -1, sizeof(hate));
  memset(city_s, 0, sizeof(city_s));
  memset(city_hate, 0, sizeof(city_hate));
  sum_s = 0;
  memset(f, 0, sizeof(f));
  memset(g, 0, sizeof(g));
  memset(h, 0, sizeof(h));
  memset(t1, 0, sizeof(t1));
  memset(t2, 0, sizeof(t2));
  ans = 0;
  ss = sc = 0;

  n = rd(), c = rd(), C0 = rd(), C1 = rd(), D0 = rd(), D1 = rd();
  for (int i = 1; i <= n; ++i) {
    b[i] = rd(), s[i] = rd();
    city_s[b[i]] += s[i];
    sum_s += s[i];
  }
  K = rd();
  for (int i = 1; i <= K; ++i) {
    int x = rd(), p = rd();
    hate[x] = p;
    city_hate[b[x]] = 1;
  }

  f[0] = 1;
  for (int i = 1; i <= c; ++i) {
    if (city_hate[i] || !city_s[i]) continue;
    for (int j = C0; j >= city_s[i]; --j)
      check(f[j] += f[j - city_s[i]]);
  }

  g[0] = 1;
  for (int i = 1; i <= n; ++i) {
    if (hate[i] != -1 || !s[i]) continue;
    for (int j = D0; j >= s[i]; --j)
      check(g[j] += g[j - s[i]]);
  }

  h[0][0] = 1;

  for (int city = 1; city <= c; ++city) {
    if (!city_hate[city]) continue;

    sc = std::min(sc + city_s[city], C0);

    for (int i = 0; i <= sc; ++i)
      for (int j = 0; j <= ss; ++j)
        t1[i][j] = t2[i][j] = h[i][j];

    for (int school = 1; school <= n; ++school) {
      if (b[school] != city || hate[school] == -1)
        continue;
      ss = std::min(ss + s[school], D0);
      for (int i = sc; ~i; --i) {
        for (int j = ss; ~j; --j) {
          check(t1[i][j] = (j >= s[school] ? t1[i][j - s[school]] * (hate[school] != 0): 0) + t1[i][j] * (hate[school] != 1));
          check(t2[i][j] = (j >= s[school] ? t2[i][j - s[school]] * (hate[school] != 2): 0) + t2[i][j] * (hate[school] != 3));
        }
      }
    }

    for (int i = 0; i <= sc; ++i) {
      for (int j = 0; j <= ss; ++j) {
        check(h[i][j] = (i >= city_s[city] ? t1[i - city_s[city]][j] : 0) + t2[i][j]);
      }
    }

  }

  for (int i = 1; i <= C0; ++i)
    check(f[i] += f[i - 1]);
  for (int i = 1; i <= D0; ++i)
    check(g[i] += g[i - 1]);

  for (int i = 0; i <= sc; ++i) {
    for (int j = 0; j <= ss; ++j) {
      check(ans += 1ll * h[i][j] * calc_f(i) % P * calc_g(j) % P);
    }
  }

  std::cout << ans << std::endl;

}

int main() {
  int T = rd();
  while (T--)
    solve();
  return 0;
}

发表评论

电子邮件地址不会被公开。必填项已用 * 标注