Coder Space

PKU 1837 Balance --- 动态规划

题意:在天平臂指定位置的勾上挂上一定重量的物品,问能使天平平衡的挂法的数量。

解法:求所有挂法,DFS暴搜可解,但解空间太大,复杂度20^20次方。
            从状态入手,已知一个状态,再挂上一个物品,得到的平衡度只与原状态平衡度有关。从而可得动态规划方程:
            DP[i][j]表示挂完前i个物品时,平衡度有j的挂法的数量。j为负表示左边重,为正表示右边重。最极端情况,所有物品挂在同一端最远处,此时平衡度度15*25*20=7500。故申请数组DP[0..20][0..15000],初始DP[0][7500]表示没放物体时,平衡度为0有一种挂法,即什么都不挂。
            复杂度O(C*G*15000)。

           
源代码

posted on 2010-08-06 12:04 David Liu 阅读(85) 评论(0)  编辑 收藏 引用 所属分类: 动态规划


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


My Links

Blog Stats

常用链接

留言簿

文章分类

文章档案

搜索

最新评论