配点: 1000 点
注意
这个问题在第 2.4 节(计算复杂性和穷举搜索)和第 3.7 节(动态规划)中都有讨论。
请注意,即使您使用全搜索解决问题,您也只能获得 500 分(满分 1000 分),并且不会获得满分(AC)。 (正如书中所说,一些大型案件无法在现实的时间内得到答复。)
問題文
N 卡片水平排列。从左边开始 i 番目 (1 \leq i \leq N) 卡有一个整数 A_i 已经写好了。
选择一些卡片,总数正好是 有办法做到 S 吗? 如果您能解决
制約
- 1 \leq N \leq 60
- 1 \leq A_i \leq 10000
- 1 \leq S \leq 10000
- 输入全为整数。
部分点
- 1 \leq N \leq 20 ,500 您可以获得积分。
入力
输入如下格式从标准输入给出。
N S A_1 A_2 A_3 \dots A_N
出力
总计
如果有办法让 S 如果有办法做到的话 Yes,否则 No 。
在第
入力例 1
3 11 2 5 9
出力例 1
Yes
卡 如果选择 1, 3 ,总计将为 11 ,所以答案是肯定的。
入力例 2
4 11 3 1 4 5
出力例 2
No