动态规划经典为题
给出不同的砝码,可以悬挂在天平的不同位置,求出可以保持天平平衡的悬挂种数
Balance
Time Limit:1000MS |
|
Memory Limit:30000K |
Total Submissions:4309 |
|
Accepted:2521 |
Description
Gigel has a strange "balance" and he wants to poise it. Actually, the device is different from any other ordinary balance.
It orders two arms of negligible weight and each arm's length is 15. Some hooks are attached to these arms and Gigel wants to hang up some weights from his collection of G weights (1 <= G <= 20) knowing that these weights have distinct values in the range 1..25. Gigel may droop any weight of any hook but he is forced to use all the weights.
Finally, Gigel managed to balance the device using the experience he gained at the National Olympiad in Informatics. Now he would like to know in how many ways the device can be balanced.
Knowing the repartition of the hooks and the set of the weights write a program that calculates the number of possibilities to balance the device.
It is guaranteed that will exist at least one solution for each test case at the evaluation.
Input
The input has the following structure:
• the first line contains the number C (2 <= C <= 20) and the number G (2 <= G <= 20);
• the next line contains C integer numbers (these numbers are also distinct and sorted in ascending order) in the range -15..15 representing the repartition of the hooks; each number represents the position relative to the center of the balance on the X axis (when no weights are attached the device is balanced and lined up to the X axis; the absolute value of the distances represents the distance between the hook and the balance center and the sign of the numbers determines the arm of the balance to which the hook is attached: '-' for the left arm and '+' for the right arm);
• on the next line there are G natural, distinct and sorted in ascending order numbers in the range 1..25 representing the weights' values.
Output
The output contains the number M representing the number of possibilities to poise the balance.
Sample Input
2 4
-2 3
3 4 5 8
Sample Output
2
分享到:
相关推荐
北大POJ1837-Balance
POJ1837-Balance 解题报告+AC代码
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
Poj 3342 这是一道树状dp题目,题意是这样的,一个公司,每个人有且仅有一个Boss,除了最大的Boss没有Boss(显然),现在要参加一个聚会,要求参加的人数最多,但是棘手的.......
这道题关键是要能够表示出状态转移方程 从题目想到这一步不容易
这是一道很不错的题目,dp解决的经典例子,是学习dp,和练习的好题目。。。。
这是黑不来就的poj上的所有dp题目的大型分类 好使好用
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
POJ1321棋盘问题 很好两种解法很值得去参考一下 完整的实验报告还有代码希望kan
放炮问题,北大网站 POJ 1185 算法
北大POJ1015-Jury Compromise【动态规划DP】 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj2342,树形dp,dp[i][0]表示i不参加party,其下属(包括非直接下属)能得到的最优值。dp[i][1]表示i参加的其下属和他能得到的最优值。
北大POJ3411-Paid Roads【class】 解题报告+AC代码
O(nlogn)凸包问题 poj2187
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1004-Financial Management 解题报告+AC代码
poj分类poj分类poj分类poj分类
POJ1048,加强版的约瑟夫问题 难度中等
2遍dp poj_3613解题报告 poj_3613解题报告