DP做题记录

· · 个人记录

*1. [APIO2016] 划艇

值域很大：对区间端点进行离散化。记为 p_1,p_2,…,p_c 。

将区间 [a_i,b_i] 变成 [a_i,b_i+1) ，方便计算答案。

设 f_{i,j} 表示第 i 个学校派出划艇数量在 L_j=[p_j,p_{j+1}) 之间时的方案数。

f_{i,j}=∑_{pos=0}^{i-1}∑_{k=0}^{j-1}f_{pos,k}×(_{m}^{m-1+L_j}),[p_j,p_{j+1})⊆[a_i,b_i)

枚举最右端不在区间 j 的位置 pos ，那么剩下来 i-pos 个位置，假设其中有 m 个位置满足可以在区间 j 上，那么方案数就是在 m-1 个 -1 和 L_j 个数 p_j,p_j+1,…,p_{j+1}-1 中选 m 个（因为第 i 个位置必选，所以至多有 m-1 个 -1 ； -1 相当于不选）。

考虑前缀和优化 s_{i,j}=∑_{k=0}^{j}f_{i,k} 。

O(1)$ 求组合数 $(_{m+1}^{m+L_j})=(_{m}^{m-1+L_j})× \frac{m+L_j}{m+1}

2. P7091 数上的树

首先把n分解质因数，然后再dfs求出 n 的因数，记为 d_1,d_2,…,d_c ，通过反素数可以得出c的值最大不会超过23327。

设 f_i 为当前子树根节点为 d_i 时的最小贡献。

由于这题局部最优可以保证全局最优，且转移无后效性（即求 f_i 时不会影响到 f_j (d_j<d_i) ，故答案可以用树形DP求出，将所有因数排序后可以转化为序列上的DP。

对于不能出现在序列中的 d_i 直接跳过即可。

设 g_i 为子树根节点为 d_i 时的节点个数（包括当前子树根节点），也就是 d_i 的因数个数，因此 g_i 的值是确定的。

假设当前转移 f_i 的决策点为 j,k(d_j×d_k=d_i) ,那么对于 d_j 和 d_k 子树内两两组合的pairs的贡献可以直接由 f_j+f_k 推出，剩下来只有两种新的情况：

1） d_j 和 d_k 子树内各出一个组成pair，因为它们的LCA是 d_i ，共有 g_j×g_k 种组合，所以贡献为 g_j×g_k×d_i 。

2）d_i 和任意一个节点（包括自己）组成pair，贡献为 g_i×d_i 。

其中 g_i=g_j+g_k+1 由其性质可以直接推出。

此时时间复杂度是 O(c^3) ，因此需要剪枝：

1）不难看出 k 具有单调性，在枚举 j 的时候可以直接用指针代替 k 。

2）当 j>k 时直接break，减小常数。

3. CF1156F Card Bag

发现我们只关心卡片上的数字的值，所以开个桶直接维护数字 i 出现的次数。又因为无后效性，所以考虑DP。

设 f_{i,j} 表示抽的第 j 张卡片上的值为 i 的概率， sz_i 表示数字 i 出现的次数。

f_{i,j}=\sum_{k=1}^{i-1}f_{k,j-1}\times\frac{sz[i]}{n-j+1}

此时时间复杂度是 O(n^3) ，因此需要前缀和优化掉 \sum_{k=1}^{i-1}f_{k,j-1} 。

设 s_{i,j}=\sum_{k=1}^{i}f_{k,j}，那么 f_{i,j}=\frac{s[i-1][j-1]\times sz[i]}{n-j+1} ，对答案做出的贡献就是 f_{i,j}\times\frac{sz[i]-1}{n-j}（取到第 j+1 张卡片的时候胜利，预处理逆元，显然 j=n 时 inv[0]=0不会统计答案，因此不需要担心会取到第 n+1 张卡片）。

可以用滚动数组把空间优化到 O(n) 。

4. [AGC013D] Piling Up

这题本质上只有四种可能的操作，因为排列中球的顺序是没有意义的：

1）拿出黑球，放入黑球 & 白球，拿出黑球

2）拿出黑球，放入黑球 & 白球，拿出白球

3）拿出白球，放入黑球 & 白球，拿出黑球

4）拿出白球，放入黑球 & 白球，拿出白球

通过画 排列中白球个数-操作次数 折线图，可以看出，如果只考虑白球数目（每次操作后，排列中球的总数不会变，黑球的数量就是总球数减去白球数目），操作 1 的最终结果是让白球数目增加 1 ，操作 2,3 不会影响球的数目，操作 4 则会让球的数目减 1 。

从一种排列开始，按照四种操作分别转移，显然可以统计出从一个点开始的所有情况并且不会重复。

于是设 f_{i,j} ，表示操作了 i 次，序列中有 j 个白球的情况总数。

现在考虑如何处理初始状态：

首先，从一个点出发的所有状态是不重复的，那么重复一定存在于从不同点出发的路径中，且一定可以通过上下平移得到。

假设在只统计白球数目达到过 0 的情况时，统计仍然有重复，设重复统计的这两条路径记为 f(x),g(x) 。因为能通过上下平移得到，所以两者关系为 f(x)=g(x)+k。

当 f(x)=0 时， g(x)=-k ，因为 g(x) 有意义，所以 g(x)=-k≤0 。

当 g(x)=0 时， f(x)=k≥0 。

因此，在 f(x),g(x) 均有白球数达到过 0 的情况时，只有 k=0 ，才有 f(x)=g(x) ，也就是说不存在重复情况。

多设一维表示当前状态的白球数目曾经是否达到过 0 即可。

5. FZOJ4397 背包

有两种背包的操作可以做到复杂度 O(m) ：

考虑分治，对于一段背包的区间 [l,r] ，如果足够小，可以暴力所有的询问；否则可以取中点 mid=\frac{l+r}{2} ，从 mid 往两边分别做前缀/后缀背包。

那么此时每个过中点的询问可以视为，两个已处理出来的背包合并后询问价格总和不超过m的答案，可以直接 O(m) 解决。

如果此时没有过中点的询问，可以分治解决 [l,r] 和 [m+1,r]。

复杂度 O(nmlogn+qm)。

6. [USACO16OPEN] 262144 P

似乎是简单题，但是有很妙的“倍增”思想。

设 f_{i,j} 表示，左端点为 j 时，往右合并，合并出数字 i 时的右端点下标。

那么就可以得到状态转移方程 f_{i,j}=f_{i-1,f_{i-1,j}}