PKU1837 Balance(DP)

http://acm.pku.edu.cn/JudgeOnline/problem?id=1837
给出一个称所有钩子位置（数组pos存），一些砝码的重量（数组w存），求全部砝码要使用并使称平衡的放法总数。
力矩=力*距离
用dp[i][k]表示前i种砝码产生力矩为k的放法，考虑第i+1种砝码，有dp[i+1][k+w[i]*pos[j]]=sigma(dp[i][k])。
三重循环穷举，最后输出dp[n][0]即可。
动态规划，真的很神奇！

posted on 2010-05-28 17:53 CisJiong 阅读(226) 评论(0)  编辑 收藏 引用 所属分类: PKU 、DP


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


导航

<2010年5月>
日一二三四五六
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

统计

常用链接

留言簿(2)

随笔分类(16)

随笔档案(11)

最新随笔

最新评论