题解
令dp[i]表示n=i时的答案。我们以n=4为例说明解法。
首先考虑两种特殊情况,如下图所示:
![](https://zh.xloypaypa.pub/content/images/2021/05/image-13.png)
![](https://zh.xloypaypa.pub/content/images/2021/05/image-14.png)
如果外面包一层。则我们可以立刻想到dp[n]=2+dp[n-1]+?
![](https://zh.xloypaypa.pub/content/images/2021/05/image-10.png)
接着,如果包两层。则我们知道dp[n]=2+dp[n-1]+dp[n-2]+?
![](https://zh.xloypaypa.pub/content/images/2021/05/image-11.png)
以此类推,可得$dp[n]=2+\sum_{i=1}^{n-1}{dp[i]}+?$
现在还有最后一种可能:将n=4拆成两个n=2且每一段的长度都一样的情况。因此每有一个n的因数就有一个新的解。
![](https://zh.xloypaypa.pub/content/images/2021/05/image-12.png)
综上,$dp[n]=2+\sum_{i=1}^{n-1}{dp[i]}+count\_of\_factor[n]$。
代码
Java
Submission #117253890 - Codeforces
Codeforces. Programming competitions and contests, programming community
![](https://codeforces.org/s/15761/images/codeforces-telegram-square.png)
C++
Submission #117257391 - Codeforces
Codeforces. Programming competitions and contests, programming community
![](https://codeforces.org/s/15761/images/codeforces-telegram-square.png)