RT,我看的出来是DP,可是转移方程是什么?
【题目描述】
有一个天平,以天平支点为0点,左右两边各有若干个钩子,总共有C个钩子,每个钩子有相对于中心的距离,如果距离为负数,表示钩子在0点左侧,如果距离为正数,表示钩子在0点右侧。 每个钩子下面可以挂若干个砝码,现在有G个法码,求将法码全部挂到钩子上时,能够使天平平衡的方法的总数。
钩子位置互不相同,砝码可能有相同重量。
【输入格式】
第1行,2个正整数*C,G,以空格分隔,表示钩子数和砝码数
第2行,C个整数x1,x2,......xc
第3行,GG个整数m1,m2......mg,以空格分隔,表示每个砝码的重量。
【输出格式】
输出一个整数,天平平衡的方法数
【样例】
输入
2 4
-2 3
3 4 5 8
输出
2
【样例解释】
有两个钩子:一个在左侧2单位距离,另一个在右侧3单位距离。
可以将重3、4、5的砝码挂在左边距离2的钩子下,重8的砝码挂在右边距离3的钩子下。
也可以将重4、8的砝码挂在左边距离2的钩子下,重3、5的砝码挂在右边距离3的钩子下。
以上两种方法都可以使天平平衡。
说明/提示
02 ≤ C,G ≤ 20
-15 ≤ x1 < x2 < ...... < xc ≤ 15
1 ≤ m1 ≤ m2 ≤ ...... ≤ mg ≤ 25