POJ 1743 Musical Theme(后缀数组+二分答案)
【题目链接】 http://poj.org/problem?id=1743
【题目大意】
给出一首曲子的曲谱,上面的音符用不大于88的数字表示,现在请你确定它主旋律的长度,主旋律指的是出现超过一次,并且长度不小于5的最长的曲段,主旋律出现的时候并不是完全一样的,可能经过了升调或者降调,也就是说,是原来主旋律所包含的数字段同时加上或者减去一个数所得,当然,两段主旋律之间也是不能有重叠的,现在请你求出这首曲子主旋律的长度,如果不存在请输出0。
HDU 5769 Substring(后缀数组)
【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5769
【题目大意】
在一个串中求出包含字母的子串个数,只要存在一个字符不相等的子串即可视为不同的子串。
BZOJ 1096 [ZJOI2007]仓库建设(斜率优化DP)
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1096
【题目大意】
有个斜坡,有n个仓库,每个仓库里面都有一些物品,物品数目为p,仓库位置为x,修缮仓库需要的费用为c,现在下雨了,之后修缮的仓库才能放东西,别的地方的仓库要运东西过来,但是只能往比它地势低的运,问所有物品得到保障的最小代价。