cf1348 E. Phoenix and Berries（dp）

https://codeforces.com/contest/1348/problem/E

題意：

有 \(n\) 棵樹，第 \(i\) 棵樹上有 \(a_i\) 個紅果和 \(b_i\) 個藍果。一個籃子的容量為 \(k\) ，一個籃子裡的果子有兩種可能：

第一種：來自同一棵樹，可以異色；

第二種：同色，但可以來自不同的樹。

求能夠被裝滿的籃子數量的最大值（不必用完所有梅子）

\(n,k\le 500\)，$a_i,b_i\le 1e9 $

思路：

首先，如果無視規則，最多能放滿 \(\lfloor\frac{\Sigma_{i=1}^n(a_i+b_i)}{k}\rfloor\) 個籃子（這是理論最大值）。如果不采用把同一棵樹上的紅藍果放一起的放法，隻把相同顔色的放一起，能放滿 \(\lfloor\frac{\Sigma_{i=1}^na_i}{k}\rfloor + \lfloor\frac{\Sigma_{i=1}^nb_i}{k}\rfloor\) 。發現後者至多比前者少1，相當于把相同顔色放一起後，再選一棵樹來放滿一個異色籃子。 另有一種 \(O(nk)\) 做法，等我學會了來更新

注意 \(n,k\) 都比較小，可以用 \(O(nk^2)\) 的 dp

一棵樹最多産生一個異色籃子。因為如果有兩個異色籃子，就一定能變成一個同色籃子和一個異色籃子。

\(bool\) \(dp[i][j]\) 表示隻考慮前 \(i\) 棵樹（後面的樹就當不存在），能否有 \(j\) 個未配置設定的紅果（即未被放進任何一種籃子）。如果未配置設定的紅果數大于等于 \(k\) ，就可以拿出來填充更多的籃子，是以 \(j<=k-1\) 。同理，未配置設定的藍果數也不會超過 \(k-1\) 。是以籃子數 \(ans=\lfloor \frac{果子總數-j}{k} \rfloor\) ，不需要考慮藍果了

假設 \(dp[i][j]=1\) ，那麼第 \(i+1\) 棵樹可能有兩種情況：

完全沒有異色籃子，那麼剩下 \((a_{i+1}+j)\%k\) 個紅果未配對。 \(dp[i+1][(a_{i+1}+j)\%k]=1\)

有一個異色籃子，其中有 \(l\) 個紅果，\(0\le l\le min(k,a_{i+1})\)。如果藍果的數量夠用也就是 \(l+b_{i+1}>=k\) ，那麼 \(dp[i+1][(a_{i+1}-l+j)\%k]=1\)

最後輸出滿足 \(dp[n][j]==1\) 的 \(ans\) 的最大值