比赛的时候想错方向了:disappointed:
Solution #
设从里向外多边形的边数为e1,e2,…,en。不难发现ei必须是ei−1的倍
数,因此我们可以把e写成e1⋅1,e1⋅k2,…,e1⋅kn。所以
如果我们知道最里面的多边形的边数,那么剩下的事情就是找到最长的序列k1=1,k2,k3,…,kn 使得ki是ki−1的倍数并且∑iki=K。
注意k2,k3,…,kn都是k2的倍数,所以如果我们把它们都除以k2就又得到
了一个以1开头的序列!也就是说我们得到了一个更小的子问题,所以我们可以用动态规
划来解决:设dpi为和为i的上述序列的最大长度。因为我们可以把一个短的序列乘上
一个数并在最前面放一个1,从而得到一个更长的序列,所以状态转移就是:
dpk⋅i+1:=max(dpk⋅i+1,dpi+1),k=2,3,…
代码 #