1.题意简述
某天小 \(x\) 去食堂吃饭，手里有 \(n\) 种饭票，面值分别为 \(A_1～A_n\) ,数量分别为 \(C_1～C_n\) 请你计算小 \(x\) 的饭票能组成多少在 \([1,m]\) 区间内的面值。
2.样例解释
3 10
1 2 4 2 1 1
8
样例中，我们有两张一元，一张两元和一张四元，可以凑出 \(1\) 到 \(8\) 元中所有面值,故答案为 \(8\)。
3.思路
1.90分思路
我们先定义一个长度为 \(m\) 的布尔数组，用于存储每种面值是否被凑到过，在最开始将 \(0\) 元打上逻辑真标记，表示 \(0\) 元可以被凑出。
然后对于第 \(i (1 \leq i \leq n)\) 种面值 \(a_i\) 何其对应张数 \(c_i\)， 只需从之前打上标记的所有面值出发重复 \(c_i\) 次将比当前点大 \(a_i\) 的点打上逻辑真，最后遍历整个数组输出逻辑真的个数即可。
代码如下：
dp[0] = 1;
v.push_back (0);
For (i, 1, n) {
p = 0, len = v.size ();
for (int j = 0; j < len; j ++) {
int now = v[j];
for (int k = 1; k <= a[i].c; k ++) {
if (now + a[i].a * k > m) break;
if (dp[now + a[i].a * k] == 0) {
ans ++;
dp[now + a[i].a * k] = 1;
v.push_back (now + a[i].a * k);
}
}
}
}
cout << ans << endl;
2.100分思路
还是可以定义逻辑数组存储面值是否能凑到，还是将面值 \(0\) 标记为1，不同的是这次我们在遍历 \(n\) 的点时再直接枚举面值，也就是说从 \(1\) 枚举到 \(m\)，在之前已经能凑出来的面值的基础上加上当前饭票面值 \(a_i\)。
如果新凑出的面值之前没有凑出过且在 \(1\) 到 \(m\) 的范围内，就将 \(ans\) 加上1。
我们新开一个 \(dp[i][j]\) 数组，表示若要凑出 \(j\) 元面值需要多少张 \(a_i\) 元饭票（变相说明 \(dp_{(i, j=(1,2,3...m)} \leq c_i\) ）所以当每次能更新时，就用如下状态转移方程：$$dp_{(i,j+a_i)} = dp_{(i,j)} + 1$$
此外还要注意一点：即使这个点已经被凑出来，但代进去不满足上述方程，也需要更新一下。。。
3.代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
//define int long long
using namespace std;
#define N 100010
#define For(i,j,k) for(int i=j;i<=k;i++)
#define IOS ios::sync_with_stdio(),cin.tie(),cout.tie()
int n, m, ans = 0, dp[110][100010];
bool ok[N];
struct no {
int a, c;
}a[N];
int main () {
IOS;
cin >> n >> m;
For (i, 1, n) cin >> a[i].a;
For (i, 1, n) cin >> a[i].c;
ok[0] = true; //将面值 0 标记为true
For (i, 1, n) {
For (j, 0, m) { //从面值0枚举到面值m
if (ok[j] && dp[i][j] < a[i].c) {
//如果面值j已被凑出来过，且接下来凑出的面值确保使用不超过 c[i] 张
if (!ok[j + a[i].a] && j + a[i].a <= m) {
//如果接下来凑出来的面值之前没有凑出来过，并且在 1~m 的范围内
ans ++; //记录结果
ok[j + a[i].a] = true; //标记面值为true
dp[i][j + a[i].a] = dp[i][j] + 1;
//面值j使用的饭票数量是它派生出的面值的使用饭票数量+1
} else if (dp[i][j + a[i].a] > dp[i][j] + 1){
//如果已经被凑出来过，但是不满足方程
dp[i][j + a[i].a] = dp[i][j] + 1;
//维护一下数组，令其符合方程
}
}
}
}
cout << ans << endl; //输出
return 0;
}
4.一个可以有的小优化
事实上，在循环时 \(dp\) 数组的第一维并没有派上用场，所以我们可以将 \(dp\) 数组开成一维的，并在每次清空一下即可，这样一来可以大大减小空间复杂度，但对应的，时间复杂度也会更高。
下面是开了二维与不开二维的区别 (\(c++ 17\))：
开了二维：
不开二维：