共48道题，当前是第26题

初赛真题

01 #include <iostream>
02 #include <algorithm>
03 #include <stdio.h>
04 using namespace std;
05 int w[35000], d[35000], dp[35000];
06 int main() {
07     int n, m;
08     scanf("%d%d", & n, & m);
09     for (int i = 1; i <= n; i++)
10         scanf("%d%d", & w[i], & d[i]);
11     for (int i = 1; i <= n; i++) {
12         for (int j = m; j >= w[i]; j--) {
13             dp[j] = max(dp[j], dp[j - w[i]] + d[i]);
14         }
15     }
16     printf("%d\n", dp[m]);
17     return 0;
18 }

1. B。 2. A。 3. A。 4. B。 5. D。 6. C。 该段程序是在通过背包 DP 的方式求解 01 背包，所以内层的 for 循环顺序是不能改变的，否则就变成完全背包了。关于越界问题有两种越界：数组越界、数据越界。如果输入的数值过大会使得 dp 数组的 int 不足以储存答案。时间复杂度为 $O(nm)$

Question

1. 上述代码中，双重循环里循环变量 j 的枚举顺序改为从 w[i] 到 m ，输出结果一定不变（ ）

2. 上述代码中，双重循环中变量 i 的枚举顺序改为从 n 到 1 ，输出结果一定不变（ ）

3. 若输入数据中，$1 <= n <= 30000,1 <= m <= 30000,1 <= w[i] <= 30000,1 <= d[i] <= 30000$,则所求答案一定没有溢出（ ）

4. 若输入数据中 $1 <= n <= 30000, 1 <= m <= 30000, 1 <= w[i] <= 30000, 1 <= d[i] <= 1e9$ 则所求答案一定没有溢出（ ）

5. 当输入为：
4 6
1 4
2 6
3 12
2 7
输出为（ ）

6. 上述代码的时间复杂度为（ ）