CSP-S2019-day2
dp专场?! /jk
pts: 64
T1: 64
T2: 0/20
T3: 0
T1
[CSP-S2019] Emiya 家今天的饭
数论,数学,容斥,dp
solution
32pts: 直接暴力枚举,选哪些食材,并判断某类食材是否超标就好了 代码
48pts: 考虑 \(m = 2\) 的情况,只有两种食材,所以每种食材选的次数必须相等,直接 \(dp\),\(f[i][j][k]\) 表示当时正在决策的烹饪方法,选了 \(j\) 个食材一和 \(k\) 个食材二的方案数代码
64pts: 考虑\(m = 3\) 的情况,和 \(m = 2\) 的情况一个样,
84pts: 对于一种做菜方案,最多只有一种主要食材在超过\(\lfloor\frac{k}{2}\rfloor\)道菜中出现过。因此考虑将答案转化为计算总不合法方案数,用总方案数减去不合法方案数即可
于是便有了一个 \(O(mn^3)\) 的做法:枚举主要食材,\(f[i][j][k]\) 表示前 \(i\) 种烹饪方式中包含\(j\) 道主要食材,有 \(k\) 种烹饪方式没有使用的方案数,\(dp\) 即可。
100pts: 如果 \(t>\lfloor\frac{k}{2}\rfloor\) 则 \(2*t>k\) ,得 \(2*t+(n-k)>n\)
因此可以将原来使用某种主要食材的菜看做使用了两次该食材,并为每种烹饪方式加一种名叫 “不选” 的菜,其使用了所有的主要食材各一次,所有使用某种主要食材大于 \(n\) 次的方案即为不合法方案 代码
T2
[CSP-S2019] 划分
贪心,单调队列,dp
solution
32pts: 最后忘了把调试输出的 \(F\) 删掉因此爆 0/kk 很简单的一个 dp, \(f[i][j]\) 表示到第 \(i\) 个数,上一个次在 \(j\) 点划分的最大方案;
转移: \(f[i][j] = min(f[j][k] + (sum[i] - sum[j]) * (sum[i] - sum[j]))\)
条件:\(sum[i] - sum[j] > sum[j] - sum[k]\)
时间复杂度: \(O(n^3)\)
64pts: 发现 \(k\) 的作用只是判断转移过来的状态合不合法,所以我们可以再开一个数组把这一维滚掉,\(last[i]\) 表示到 \(i\) 到上一个端点 \(j\) 之间的和,\(last\) 可以在转移的时候可以顺便求出来 代码
时间复杂度:\(O(n^2)\)
100pts: 贪心发现段分的越多答案越小,\(f[i]\) 表示到 \(i\) 点前的最后一个端点,显然要使得 \(f[i]\) 尽可能的靠近 \(i\)
\(f_i\) 一定是单调不降的,合法的条件为 \(sum_i - sum_j\geq sum_j - sum_{f_j}\),可以变形为 \(sum_i\geq sum_j+(sum_j-sum_{f_j})\) 根据题意,\(sum_j-sum_{f_j}\) 和 \(sum_j\) 具有单调性。显然,这可以用单调队列来维护 \(f_i\) 的值 代码
复杂度 \(O(n)\)
T3
[CSP-S2019] 树的重心
树形 dp
solution