P2037 [第二章习题1.5]Beads
Zxl 有一次决定制造一条项链,她以非常便宜的价格买了一长条鲜艳的珊瑚珠子,她现在也有一个机器,能把这条珠子切成很多块(子串),每块有 k个珠子,如果这条珠子的长度不是 k的倍数,最后一块小于 k的就不要拉(真浪费),保证珠子的长度为正整数。Zxl 喜欢多样的项链,为她应该怎样选择数字 k来尽可能得到更多的不同的子串感到好奇,子串都是可以反转的,换句话说,子串 (1,2,3) 和 (3,2,1) 是一样的。写一个程序,为 Zxl 决定最适合的 k从而获得最多不同的子串。
例如这一串珠子是 (1 1 1 2 2 2 3 3 3 1 2 3 3 1 2 2 1 3 3 2 1)
k=1 时可得 3个不同的子串:(1) (2) (3)
k=2 时可得 6个不同的子串:(1,1) (1,2) (2,2) (3,3) (3,1) (2,3)
k=3 时可得 5个不同的子串:(1,1,1) (2,2,2) (3,3,3) (1,2,3) (3,1,2)
k=4 时可得 5个不同的子串:(1,1,1,2) (2,2,3,3) (3,1,2,3) (3,1,2,2) (1,3,3,2)
21
1 1 1 2 2 2 3 3 3 1 2 3 3 1 2 2 1 3 3 2 1
6 1 2