注意:我仍在寻找快速解决方案.下面的两个解决方案是错误的,第三个解决方案非常慢.
我有1个N玩具.... N. 每个玩具都有相关的成本.你必须疯狂购物,在某一天,如果你买玩具我,那么你可以在同一天购买的下一个玩具应该是i + 1或更高.此外,任何两个连续购买的玩具之间的绝对成本差异应大于或等于k.我可以购买所有玩具的最小天数是多少.
我尝试了一种贪婪的方法,首先从玩具1开始,然后看看我可以在第1天购买多少玩具.然后,我找到了我没有买过的最小的i,然后从那里重新开始.
例:
Toys : 1 2 3 4
Cost : 5 4 10 15
设k为5
在第1天,在第2天购买1,3和4,购买玩具2
因此,我可以在2天内购买所有玩具
注意贪婪不适用于以下示例:N = 151和k = 42玩具的成本1 ... N依次为:
383 453 942 43 27 308 252 721 926 116 607 200 195 898 568 426 185 604 739 476 354 533 515 244 484 38 734 706 608 136 99 991 589 392 33 615 700 636 687 625 104 293 176 298 542 743 75 726 …对于两个字符串A和B,我们将字符串的相似性定义为两个字符串共有的最长前缀的长度.例如,字符串"abc"和"abd"的相似性是2,而字符串"aaa"和"aaab"的相似性是3.
问题是给出一个算法来计算字符串S与每个后缀的相似之和.例如,让字符串为:ababaa.然后,该字符串的后缀ababaa,babaa,abaa,baa,aa和a.每个这些字符串与所述串的的相似之处ababaa是6,0,3,0,1,1,分别.答案是这样的6 + 0 + 3 + 0 + 1 + 1 = 11.