| Time Limit: 1000MS | Memory Limit: 30000K | |
| Total Submissions: 11161 | Accepted: 6938 |
Description
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 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
Sample Input
2 4 -2 3 3 4 5 8
Sample Output
2
Source
解题思路：
QAQ，20多天不写题，连这个简单的dp都切不出来了，最后在凯巨巨的指导下，，，才完成了这20多天来的第一次AC，
先说说题目吧。题目就是说，有一个天平，这个天平的中点是原点，然后输入挂钩的数目和砝码的重量，最后得的能够
使得天平平衡的方法总数，总的来看有点像枚举，但是枚举出来的结果肯定会T，于是就往dp上想，最开始的时候，
自己定义好了状态 ： dp[i][j] 表示挂上前i个挂钩后，平衡度为j的方法总数（有点像以前做的一个过河卒问题，dp[i][j]
表示的是从（0,0）->（i，j）的方法总数）,接下来呢，我们就是对于dp[i][j]数组的大小的定义了，如果能够很好的定义
这个数组的话，那么，最后直接找dp[g][7500]就行了，为什么要找这个值呢？不要着急，慢慢来讲。
题目中说了，天平臂的最大长度是15，挂上去的最大砝码的重量是25，最多能挂20个砝码。
那么这个dp数组的最大值就是15*25*20=7500了，那么只要求-7500---7500的所有dp[i]的值，就可以得到这个天平上
挂上符合要求的砝码的个数的所有方法总数了。。。
下来就是把这张表打好，然后依次去遍历就可以得到我们要的结果了，为了不出现负数，那么，就把平衡状态定义为:
dp[i][7500]，数组的上届为7500*2
代码：
# include<cstdio>
# include<iostream>
using namespace std;
# define MAX 21
int cc[MAX];
int gg[MAX];
int dp[21][15001];
int main(void)
{
int c;//钩子的数量
int g;//砝码的数量
while ( cin>>c>>g )
{
for ( int i = 1;i <= c;i++ )
{
cin>>cc[i];
}
for ( int i = 1;i <= g;i++ )
{
cin>>gg[i];
}
dp[0][7500] = 1;
for ( int i = 1;i <= g;i++ )
{
for ( int j = 0;j <= 15000;j++ )
{
for ( int k = 1;k <= c;k++ )
if ( dp[i-1][j] )
{
dp[i][j+cc[k]*gg[i] ] += dp[i-1][j];
}
}
}
cout<<dp[g][7500]<<endl;
}
return 0;
}