随笔-72  评论-126  文章-0  trackbacks-0
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ǎ崽 阅读(340) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理