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

題目大意是：對(duì)于一組數(shù)據(jù)，它的原始序列是 1，其余的數(shù)字是由 1 衍生的數(shù)字.

例如一個(gè)數(shù)組{5,1,3,2,1}：

開(kāi)始時(shí)是 {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}.

這題沒(méi)注意細(xì)節(jié)踩了一堆大坑。。。

思路: 很明顯要先排序, 然后按照數(shù)組 c 的遞增順序來(lái)檢查, 要檢查是否能得到 c, 可以先用 dp 嘗試一下。

一開(kāi)始用dp設(shè)了兩個(gè)狀態(tài) f[i][j]: 前 i 個(gè)數(shù)中是否能得到 j, 于是我就想第 i 個(gè)數(shù)的狀態(tài)是由 i 前面的某一個(gè)數(shù) a[i - k]?轉(zhuǎn)移過(guò)來(lái)的:

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

提交后直到看到錯(cuò)誤樣例發(fā)現(xiàn) {1, 1, 1, 1, 3} 的 f[5][3] = f[4][2] ... f[2][2], 顯然根據(jù)上面的方程是得不到 f[4][2] 為 True 的. 因?yàn)榉噶艘粋€(gè)大錯(cuò)誤,?在本題中所有狀態(tài)轉(zhuǎn)移的過(guò)程中出現(xiàn)的數(shù)不一定在數(shù)組 c 中 (比如{1, 1, 1, 1, 3} 前幾個(gè)元素可以生成的數(shù)字2不在數(shù)組中, 導(dǎo)致遍歷到數(shù)字3 時(shí)只能從 1 轉(zhuǎn)移狀態(tài), 但事實(shí)是要從數(shù)字2轉(zhuǎn)移的)。

既然與位置無(wú)關(guān), 那么我們可以設(shè)置如下?tīng)顟B(tài) f[i] : 通過(guò)操作是否得到數(shù)字 i

很顯然 f[1] = true

那么我們從下標(biāo) 2 開(kāi)始遍歷, 遍歷到當(dāng)前元素 c[i] 時(shí), 如果 f[c[i]] 為 false, 那么說(shuō)明不可以生成這個(gè)數(shù)字, 返回.

否則我們要更新依靠這個(gè)狀態(tài)能生成那些數(shù)字(也就是包含這個(gè)數(shù)字的區(qū)間都能生成哪些數(shù)字), 由于最大可能是5000, 我們可以使用變量 j 從5000開(kāi)始遍歷到 c[i]:

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

注意不能從 c[i] 遍歷到 5000, 以為假設(shè)當(dāng) c[i] 為 1 且為 true 時(shí), 向上遍歷會(huì)使得 f[1] 一直到 f[5000] 全為 true, 而倒序遍歷就很好地避免了這個(gè)問(wèn)題 (看了半天答案 + 踩坑才恍然大悟。。。)