2008年7月24日星期四

ZJU/ZOJ 1234 Chopsticks 解题报告

题目大意是给出n个递增的的数,从中选出k+8组,每组三个数a、b、c(递增)使选出的∑(a+b)^2最小。

如果是顺推要处理第三个数比较麻烦,因此采用逆推的思想,用f[i,j]表示从第i到第n个数中选取j组数的∑(a+b)^2最小值。注意一个有效状态需要满足i-1>=2*(k-j)且n-i+1>=3*j,则f[i,j]=min(f[i+2,j-1]+(c[i+1]-c[i])^2,f[i+1,j])(n-i+1>3*j),f[i+2,j-1]+(c[i+1]-c[i])^2(n-i+1=3*j);空间复杂度可以用滚动数组优化到O(n)。

3003473 2008-07-24 23:08:37 Accepted 1234 FPC 00:00.55 19972K IwfWcf

6 条评论:

相关文章

 
Creative Commons License
除非另有声明,本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 许可协议授权。