求助站外题
  • 板块题目总版
  • 楼主Escapism
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/2/2 08:51
  • 上次更新2023/10/28 09:50:13
查看原帖
求助站外题
361505
Escapism楼主2022/2/2 08:51

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

2022/2/2 08:51
加载中...