十二省联考2019皮配 背包DP

发表于 更新于 分类于 阅读次数：

[十二省联考2019]皮配 题目描述太长是真的难受… 洛谷题解里有个很有意思的简化版题意：豆子有黄色绿色，圆粒皱粒。豆子有重量，每种性状的豆子有重量和上限。同时有一些豆子钦定不能有某种性状。告诉了有多少豆荚，每个豆荚里每个豆子，豆荚里豆子颜色要一样，求方案。 那么就有一种DP的想法：因为两对相对性状，和的数量都是$n$，令$f_{i,j}$表示有$i$的$C_0$，$j$的$D_0$的答案。可以$O(nm^2)$的做。又因为性状独立，当没有限制的时候可以分开做再乘起来，$O(nm)$。 因为特殊的豆子很少，考虑对没有特殊豆子的豆荚先做一个DP。对有特殊豆子的豆荚做一个高复杂度DP，组合起来。组合的话只需要枚举$i,j$，并且用前缀和优化。 考虑$f_{i,j}$的计算。虽然特殊豆子很少，但是它们所在的豆荚大小并没有给定一个小范围。那么必须考虑想办法把它们分开。那么可以考虑把整个豆荚的颜色放在一起DP，但是是圆是皱只对特殊豆子DP。 把$f$复制两份，分别表示两种颜色的方案。枚举豆荚内的特殊豆子，进行更新即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#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;
}