http://acm.hdu.edu.cn/showproblem.php?pid=1500这题目和般寝室其实是类似的
http://acm.hdu.edu.cn/showproblem.php?pid=1421不过多加了一个条件，后边还要有一根筷子
所以就不能到DP到n
要根据每次取的筷子数
算出一个max值
DP到这个max值就可以了。
max~n的值就不用dp了
其实再优化一下max~max+3就行了
由于数组很大，1000*5000的，我开了一个2*5000的滚动数组，这是我第一次用滚动数组
用异或运算很容易实现
下边的是状态转移方程
for(i++;i<=max;i++)
dp[next][i] = Min(dp[next][i-1],dp[row][i-2] + (cho[i] - cho[i-1])*(cho[i] - cho[i-1]););
for(i=max+1;i<=max+3;i++)
dp[next][i] = dp[next][i-1];
posted on 2009-02-20 11:28
shǎ崽 阅读(368)
评论(0) 编辑 收藏 引用