P5289

题目链接 点击打开链接 题目解法 题意比较复杂，形式化一下题意是： 一些人和一些城市，每个人属于一个城市，每个人属于 \(A/B/C/D\) 队，需要满足：每个城市中的人要么都属于 \(AC\) 或 \(BD\)，且 \(A+C\le C_0,\;B+D\le C_1,\;A+B\le D_0,\; ......

很容易想到设 \(dp_{i,j,k}\) 表示考虑前 \(i\) 个阵营，\(C_0=j\)，\(D_0=k\) 时的方案数，层内转移时可以用辅助数组对两种阵营决策分别转移，此时时间复杂度为 \(O(nM^2)\)。 考虑 \(k=0\) 的情况，如果我们能做这个的话，\(k=30\) 其实就是在 ......