[COCI2009-2010#4] KABOOM

_H17_ · 2024-06-12 22:36:29 · 题解

和这篇题解有些类似，但是讲的更加详细，并且有参考与这篇题解。

题目分析

这是一道 DP 题目，一开始想到区间 DP，但是发现胶太难处理了，而且没法转移，于是换方法。

不久我发现了无论如何两边胶带不可能少于 a,b 于是可以通过把胶、长度当状态作 DP。

设 f_{i,j,k} 为前后分别有 i,j 个胶，总长度为 k 的胶带数。

捣鼓半天没搞出来，而且空间不符合限制。考虑优化状态，鉴于前后都有胶带，而且前后性质相同（即都可以一起处理）。想想为什么？

于是设 f_{i,j} 表示总长度为 i 前或者后有 j 个胶的数量（另一边没有胶，可以随便折）。

由于转移过程比较难推导（个人认为），所以在下一板块【转移】。

转移

首先我们可以枚举折的长度，从而进行展开操作。折的长度至少是 j。

此时 f_{i,j}=f_{i-j,j}，然而可以折的更长，为了找到普遍规律，我们设折的长度为 j+k。

于是得到 f_{i,j}=\sum\limits_{k=0}^{(i-2\times j)\div 2}f_{i-j-k,j+k}，显然转移的时间不够优秀。

根据之前转移的依据得出：我们转移的变化量 k 纯属是根据 j 而限定范围的（提示是 f_{i,j+1}，读者可以想一想为什么，再继续阅读）。

我们发现 f_{i,j+1}=\sum_{k=1}^{(i-2\times j)\div 2}f_{i-j-k,j+k}，原因是 k=0 时就成了折 j 段胶，然而这时必须是 j+1 段胶。

鉴于这两个式子差距很小，我们可以用 f_{i,j+1} 来得到 f_{i,j}。

转移方程 f_{i,j}=f_{i,j+1}+f_{i-j,j}，前一项如上所述，后一项则是差的折 j 段胶的情况。

统计答案

由于我们的 DP 只考虑了一边，另一边答案一样。我们考虑找到一个分割点（非胶），左边和右边分别折，求总数。

注意到左边必须是严格折到 i 而非前 i 段（想一想为什么），后面可以。这样可以避免重复。

答案是 \sum\limits_{i=a}^{n-b}(f_{i,a}-f_{i-1,a})\times f_{n-i,b}。

这里解释为什么要严格折到 i，如果是前 i 段，那么前 i-1 段的值已经被统计了，这样会重复。然而后半边不会重复。

初始状态