笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

「水经验」CF1339A Filling Diamonds

posted on 2020-05-27 11:01:44 | under 题解 |

审题解的说是重复解法。我寻思着就算题简单到爆炸这也不是重复解法啊?我想要审题解的人给一个解释。

经验还是要水的。这里说一个比较直观的转移。

设 $f(n)$ 为 $n$ 时的方案数。

考虑 $n$ 每次 $+1$,可以拆成两个单独的小菱形加上 $n-1$ 的方案,那么看上去通过分类讨论在左边插入还是右边插入,答案应该为

$$ f(n)=2\cdot f(n-1) $$

但是这并不对,因为两种方式会有重复。发现重复就重复在共同使用了中间那个大小为 $n-2$ 的多边形上。于是可以知道正确的递推应该是

$$ f(n)=2\cdot f(n-1)-f(n-2) $$

归纳可得

$$ f(n)=2\cdot (n-1)-(n-2)=n $$