题目背景

uim神犇拿到了uoi的ra（镭牌）后，立刻拉着基友小A到了一家餐馆，很低端的那种。
uim指着墙上的价目表（太低级了没有菜单），说：“随便点”。

题目描述

不过uim由于买了一些辅（e）辅（ro）书，口袋里只剩 mm 元（m≤10000m \le 10000）。
餐馆虽低端，但是菜品种类不少，有 nn 种（n≤100n \le 100），第 ii 种卖 aia_i 元（ai≤1000a_i \le 1000）。由于是很低端的餐馆，所以每种菜只有一份。
小A奉行“不把钱吃光不罢休”，所以他点单一定刚好把uim身上所有钱花完。他想知道有多少种点菜方法。
由于小A肚子太饿，所以最多只能等待 11 秒。

输入格式

第一行是两个数字，表示 nn 和 mm。
第二行起 nn 个正数 aia_i（可以有相同的数字，每个数字均在 10001000 以内）。

输出格式

一个正整数，表示点菜方案数，保证答案的范围在 int 之内。

输入输出样例

输入 #1

1
2
4 4
1 1 2 2

输出 #1

1
3

说明/提示

2020.8.29，增添一组 hack 数据 by @yummy。

思路

背包问题，考虑一个菜品选或不选两种情况，类似 0−10-1 背包，但是这里是计数问题。考虑动态规划解决问题，设计状态 f(i,j,0/1)f(i,j,0/1)：f(i,j,0)f(i,j,0) 表示考虑完第 ii 个物品，当前背包内价值为 jj，且不选择第 ii 个物品的方法数；f(i,j,1)f(i,j,1) 表示考虑完第 ii 个物品，当前背包内价值为 jj，且选择第 ii 个物品的方法数。
类似 0−10-1 背包，有递推关系 f(i,j,0)=f(i−1,j,0)+f(i−1,j,1)f(i,j,0)=f(i-1,j,0)+f(i-1,j,1) 和 f(i,j,1)=f(i−1,j−ai,0)+f(i−1,j−ai,1)f(i,j,1)=f(i-1,j-a_i,0)+f(i-1,j-a_i,1)；临界条件为 f(i,0,0)=1f(i,0,0)=1 和 f(i,0,1)=0f(i,0,1)=0。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: Luogu P1164
Date: 2021 Mar. 17th
Description: Dynamic Programming
*******************************************************************/
#include<iostream>
using namespace std;
int f[103][10004][2];
int m, n;
int a[103];
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i <= n; i++) {
		f[i][0][0] = 1;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			f[i][j][0] = f[i - 1][j][1] + f[i - 1][j][0];
			if (j >= a[i]) {
				f[i][j][1] = f[i - 1][j - a[i]][0] + f[i - 1][j - a[i]][1];
			}
		}
	}
	cout << f[n][m][0] + f[n][m][1] << endl;
	return 0;
}