cf Round #859 (Div.4) G1. Subsequence Addition (贪心 + dp)

题目地址: https://codeforces.com/problemset/problem/1807/G1

题目大意是：对于一组数据，它的原始序列是 1，其余的数字是由 1 衍生的数字.

例如一个数组{5,1,3,2,1}：

开始时是 {1}，然后 {1,1}，(1+1=2)->{1,2,1}，(1+2=3)->{1,3,2,1}，(1+1+3=5)->{5,1,3,2,1}.

这题没注意细节踩了一堆大坑。。。

思路: 很明显要先排序, 然后按照数组 c 的递增顺序来检查, 要检查是否能得到 c, 可以先用 dp 尝试一下。

一开始用dp设了两个状态 f[i][j]: 前 i 个数中是否能得到 j, 于是我就想第 i 个数的状态是由 i 前面的某一个数 a[i - k] 转移过来的:

f[i][j] = f[i - k][j - a[i - k]]

提交后直到看到错误样例发现 {1, 1, 1, 1, 3} 的 f[5][3] = f[4][2] ... f[2][2], 显然根据上面的方程是得不到 f[4][2] 为 True 的. 因为犯了一个大错误, 在本题中所有状态转移的过程中出现的数不一定在数组 c 中 (比如{1, 1, 1, 1, 3} 前几个元素可以生成的数字2不在数组中, 导致遍历到数字3 时只能从 1 转移状态, 但事实是要从数字2转移的)。

既然与位置无关, 那么我们可以设置如下状态 f[i] : 通过操作是否得到数字 i

很显然 f[1] = true

那么我们从下标 2 开始遍历, 遍历到当前元素 c[i] 时, 如果 f[c[i]] 为 false, 那么说明不可以生成这个数字, 返回.

否则我们要更新依靠这个状态能生成那些数字(也就是包含这个数字的区间都能生成哪些数字), 由于最大可能是5000, 我们可以使用变量 j 从5000开始遍历到 c[i]:

f[j] = f[j] | f[j - c[i]]

注意不能从 c[i] 遍历到 5000, 以为假设当 c[i] 为 1 且为 true 时, 向上遍历会使得 f[1] 一直到 f[5000] 全为 true, 而倒序遍历就很好地避免了这个问题 (看了半天答案 + 踩坑才恍然大悟。。。)