hdu5074专题

hdu5074 Hatsune Miku

鞍山现场赛里的一道题,都说是水题,却让我花了很长时间。。。 首先我一看就知道要用dp,不过我的思路在一开始总是那么低级。。。 最开始,我想的是把任意两种音符中间间隔任意个空缺的最优值算出来,然后再扫描 s数组,直接把最优值加起来就行了。结果写了5层循环,dp数组也是3维的。估算了一下,复杂度大概在10的7次方,感觉勉强能过得。。。交了tle,现在看来,显然会tle。 第二次尝试,我还是觉得1