动态规划基础与一维动态规划

动态规划的基本思路；简单一维动态规划。

概念

动态规划把原问题拆成重叠子问题，按阶段填表，每格存最优或方案数，利用已算结果避免重复枚举。一维 DP 最常见：dp[i] 表示考虑前 i 个元素、或到达位置 i 的最优值，转移来自 dp[i-1]、dp[i-2] 或若干前驱。识别关键是「最优子结构 + 无后效性」——当前决策只依赖已记录状态。与 cspj.algo.dp-knapsack-interval 区分：后者是背包（选/不选）或区间合并类 DP；与 cspj.algo.recurrence-and-recursion 区分：递推可以是 DP 的实现方式，但 DP 强调多候选取 max/min 或计数。与 cspj.algo.greedy 区分：DP 会同时保留多种子结构的结果。

CSP-J 常考

cspj-r1-2023 第 21–22、38–42 题：阅读/完善程序，一维 DP 数组定义、转移与初值填空。
cspj-r1-2024 第 21、23–26 题：阅读程序，trace dp[i] 或完善转移式。
cspj-r1-2025 第 22–23、25–26、28–33 题：本课该叶子题量最多，完善程序与阅读程序集中考查 DP 填表。
cspj-r2-2019 第 3 题：复赛编程，逐日买卖求第 T 天最多金币，状态转移 DP。
cspj-r2-2024 第 3 题：复赛编程，每位数字固定棍数代价，构造最小正整数的一维 DP。

// 爬楼梯：到第 i 阶的方案数 = 到 i-1 + 到 i-2
int dp[20];
dp[1] = 1; dp[2] = 2;
for (int i = 3; i <= n; ++i)
    dp[i] = dp[i-1] + dp[i-2];
// 若求最小代价，转移里用 min 而非 +

易错点

初值 dp[0]、dp[1] 与题意不符，完善程序只改一行转移却忽略边界。
循环方向错：需要 dp[i-1] 已算完时，i 应从小到大；若依赖后面状态则要反过来。
把「递推求项」与「DP 求最值」混淆，阅读程序里出现 max/min 时要找决策分支。

编程题

纪念品

C++时间 1 s内存 256 MB 文件 IO：souvenir.in → souvenir.out

小伟突然获得一种超能力，他知道未来 $T$ 天 $N$ 种纪念品每天的价格。某个纪念品的价格是指购买一个该纪念品所需的金币数量，以及卖出一个该纪念品换回的金币数量。

每天，小伟可以进行以下两种交易无限次：

任选一个纪念品，若手上有足够金币，以当日价格购买该纪念品；
卖出持有的任意一个纪念品，以当日价格换回金币。

每天卖出纪念品换回的金币可以立即用于购买纪念品，当日购买的纪念品也可以当日卖出换回金币。当然，一直持有纪念品也是可以的。

$T$ 天之后，小伟的超能力消失。因此他一定会在第 $T$ 天卖出所有纪念品换回金币。

小伟现在有 $M$ 枚金币，他想要在超能力消失后拥有尽可能多的金币。

输入格式

第一行包含三个正整数 $T, N, M$ ，相邻两数之间以一个空格分开，分别代表未来天数 $T$ ，纪念品数量 $N$ ，小伟现在拥有的金币数量 $M$ 。

接下来 $T$ 行，每行包含 $N$ 个正整数，相邻两数之间以一个空格分隔。第 $i$ 行的 $N$ 个正整数分别为 $P_{i,1},P_{i,2},\dots,P_{i,N}$ ，其中 $P_{i,j}$ 表示第 $i$ 天第 $j$ 种纪念品的价格。

输出格式

输出仅一行，包含一个正整数，表示小伟在超能力消失后最多能拥有的金币数量。

样例

输入 1

输出 1

最佳策略是：

第二天花光所有 $100$ 枚金币买入 $5$ 个纪念品 $1$ ；

第三天卖出 $5$ 个纪念品 $1$ ，获得金币 $125$ 枚；

第四天买入 $6$ 个纪念品 $1$ ，剩余 $5$ 枚金币；

第六天必须卖出所有纪念品换回 $300$ 枚金币，第四天剩余 $5$ 枚金币，共 $305$ 枚金币。

超能力消失后，小伟最多拥有 $305$ 枚金币。

输入 2

输出 2

最佳策略是：

第一天花光所有金币买入 $10$ 个纪念品 $1$ ；

第二天卖出全部纪念品 $1$ 得到 $150$ 枚金币并买入 $8$ 个纪念品 $2$ 和 $1$ 个纪念品 $3$ ，剩余 $1$ 枚金币；

第三天必须卖出所有纪念品换回 $216$ 枚金币，第二天剩余 $1$ 枚金币，共 $217$ 枚金币。

超能力消失后，小伟最多拥有 $217$ 枚金币。

数据范围

对于 $10\%$ 的数据， $T = 1$ 。

对于 $30\%$ 的数据， $T \leq 4, N \leq 4, M \leq 100$ ，所有价格 $10 \leq P_{i,j} \leq 100$ 。

另有 $15\%$ 的数据， $T \leq 100, N = 1$ 。

另有 $15\%$ 的数据， $T = 2, N \leq 100$ 。

对于 $100\%$ 的数据， $T \leq 100, N \leq 100, M \leq 10^3$ ，所有价格 $1 \leq P_{i,j} \leq 10^4$ ，数据保证任意时刻，小明手上的金币数不可能超过 $10^4$ 。

部分分

100 分
全部 $20$ 个测试点等分；数据范围见 constraintsMd 各百分比档。

原文保真说明：原卷印刷错误 1 处（照原卷保留，未作修改）

原卷印刷如此符号不一致数据范围
原卷作 小明手上的金币数 ，常规写法应为 小伟手上的金币数
原卷第 7 页【数据规模与约定】末句印作「小明」，题面正文（第 6 页）与样例解释均作「小伟」。constraintsMd 按第 7 页图像照录「小明」；原卷印刷不一致已如实记录。

你的代码（C++）

提交后由评测机编译运行，结果见下方

编辑器加载中…

76 B / 64 KB

判题结果

编程题

方格取数

C++时间 1 s内存 256 MB 文件 IO：number.in → number.out

设有 $n \times m$ 的方格图，每个方格中都有一个整数。现有一只小熊，想从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。小熊会取走所有经过的方格中的整数，求它能取到的整数之和的最大值。

输入格式

从文件 number.in 中读入数据。

第一行有两个正整数 $n, m$ 。

接下来 $n$ 行，每行 $m$ 个整数，依次代表每个方格中的整数。

输出格式

输出到文件 number.out 中。

输出一行一个整数，表示小熊能取到的整数之和的最大值。

样例

输入 1

输出 1

按走法 $(1,1) \to (2,1) \to (2,2) \to (2,3) \to (1,3) \to (1,4) \to (2,4) \to (3,4)$ ，取到的数之和为 $1 + 2 + (-1) + 4 + 3 + 2 + (-1) + (-1) = 9$ ，可以证明为最大值。原卷【样例 1 解释】含路径示意图（pg-08），此处仅转写文字说明。

输入 2

2 5
-1 -1 -3 -2 -7
-2 -1 -4 -1 -2

输出 2

-10

按走法 $(1,1) \to (1,2) \to (1,3) \to (1,4) \to (2,4) \to (2,5)$ ，取到的数之和为 $(-1) + (-1) + (-3) + (-2) + (-1) + (-2) = -10$ ，可以证明为最大值。因此，取到的数之和的最大值也可能是负数。原卷【样例 2 解释】含路径示意图（pg-09）。

数据范围

对于 $20\%$ 的数据， $n, m \le 5$ 。

对于 $40\%$ 的数据， $n, m \le 50$ 。

对于 $70\%$ 的数据， $n, m \le 300$ 。

对于 $100\%$ 的数据， $1 \le n, m \le 10^3$ 。方格中整数的绝对值不超过 $10^4$ 。

部分分

100 分
全部 $20$ 个测试点等分；数据范围见 constraintsMd 各百分比档。

你的代码（C++）

提交后由评测机编译运行，结果见下方

编辑器加载中…

76 B / 64 KB

判题结果

阅读程序共 1.5 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

1 #include <algorithm>2 #include <iostream>3 #include <limits>4 5 using namespace std;6 7 const int MAXN = 105;8 const int MAXK = 105;9 10 int h[MAXN][MAXK];11 12 int f(int n, int m)13 {14 if (m == 1) return n;15 if (n == 0) return 0;16 17 int ret = numeric_limits<int>::max();18 for (int i = 1; i <= n; i++)19 ret = min(ret, max(f(n - i,m), f(i - 1, m - 1)) + 1);20 return ret;21 }22 23 int g(int n, int m)24 {25 for (int i = 1;i <= n; i++)26 h[i][1]= i;27 for (int j = 1;j<= m; j++)28 h[0][j]= 0;29 30 for (int i= 1; i <= n; i++){31 for (int j= 2; j <= m; j++){32 h[i][j] = numeric_limits<int>::max();33 for (int k = 1;k <= i;k++)34 h[i][j]= min(35 h[i][j],36 max(h[i - k][j],h[k - 1][j - 1]) +1);37 }38 }39 40 return h[n][m];41 }42 43 int main()44 {45 int n,m;46 cin >> n>> m;47 cout << f(n, m) << endl << g(n, m)<< endl;48 return 0;49 }

23判断1.5 分
输出的两行整数总是相同的。

阅读程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

25单选3 分
单选题
1. 算法 $g(n,m)$ 最为准确的时间复杂度分析结果为（）。
A
$O(n^{3/2}m)$

B
$O(nm)$

C
$O(n^{2}m)$

D
$O(nm^{2})$

阅读程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

26单选3 分
当输入为 20 2 时，输出的第一行为（）。

A
$4$

B
$5$

C
$6$

D
$20$

阅读程序共 4 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

27单选4 分
（ $4$ 分） 当输入 100 100 时，输出的第一行为（）。

A
$6$

B
$7$

C
$8$

D
$9$

编程题

上升点列

C++时间 1 s内存 512 MB 文件 IO：point.in → point.out

在一个二维平面内，给定 $n$ 个整数点 $(x_i, y_i)$ ，此外你还可以自由添加 $k$ 个整数点。

你在自由添加 $k$ 个点后，还需要从 $n + k$ 个点中选出若干个整数点并组成一个序列，使得序列中任意相邻两点间的欧几里得距离恰好为 $1$ 而且横坐标、纵坐标值均单调不减，即 $x_{i+1} - x_i = 1, y_{i+1} = y_i$ 或 $y_{i+1} - y_i = 1, x_{i+1} = x_i$ 。请给出满足条件的序列的最大长度。

输入格式

从文件 point.in 中读入数据。

第一行两个正整数 $n, k$ 分别表示给定的整点个数、可自由添加的整点个数。

接下来 $n$ 行，第 $i$ 行两个正整数 $x_i, y_i$ 表示给定的第 $i$ 个点的横纵坐标。

输出格式

输出到文件 point.out 中。

输出一个整数表示满足要求的序列的最大长度。

样例

输入 1

输出 1

输入 2

输出 2

数据范围

对于所有数据满足： $1 \leq n \leq 500$ ， $0 \leq k \leq 100$ 。对于所有给定的整点，其横纵坐标 $1 \leq x_i, y_i \leq {10}^9$ ，且保证所有给定的点互不重合。对于自由添加的整点，其横纵坐标不受限制。

测试点编号	$n \leq$	$k \leq$	$x_i,y_i \leq$
$1 \sim 2$	$10$	$0$	$10$
$3 \sim 4$	$10$	$100$	$100$
$5 \sim 7$	$500$	$0$	$100$
$8 \sim 10$	$500$	$0$	${10}^9$
$11 \sim 15$	$500$	$100$	$100$
$16 \sim 20$	$500$	$100$	${10}^9$

部分分

10 分
测试点 $1 \sim 2$ ： $n \le 10$ ， $k \le 0$ ， $x_i, y_i \le 10$ 。
10 分
测试点 $3 \sim 4$ ： $n \le 10$ ， $k \le 100$ ， $x_i, y_i \le 100$ 。
15 分
测试点 $5 \sim 7$ ： $n \le 500$ ， $k \le 0$ ， $x_i, y_i \le 100$ 。
15 分
测试点 $8 \sim 10$ ： $n \le 500$ ， $k \le 0$ ， $x_i, y_i \le 10^9$ 。
25 分
测试点 $11 \sim 15$ ： $n \le 500$ ， $k \le 100$ ， $x_i, y_i \le 100$ 。
25 分
测试点 $16 \sim 20$ ： $n \le 500$ ， $k \le 100$ ， $x_i, y_i \le 10^9$ 。

原文保真说明：来源改写 1 处（照原卷保留，未作修改）

来源题面被改写其它数据范围
原卷作 | $16 \sim 20$ | $500$ | $100$ | ${10}^9$ | ，常规写法应为 | $15 \sim 20$ | $500$ | $100$ | ${10}^9$ |
官方 PDF 第 10 页测试点表末行印作 $15 \sim 20$，与上一行 $11 \sim 15$ 重叠；结合共 $20$ 个等分测试点，恢复为 $16 \sim 20$。
已按官方原件恢复：现为原卷原文

你的代码（C++）

提交后由评测机编译运行，结果见下方

编辑器加载中…

76 B / 64 KB

判题结果

阅读程序共 1.5 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

#include<iostream>#include<vector>#include<algorithm>using namespace std;int f(string x,string y){ int m=x.size(); int n=y.size(); vector<vector<int>>v(m+1,vector<int>(n+1,0)); for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ if(x[i-1]==y[j-1]){ v[i][j]=v[i-1][j-1]+1; }else{ v[i][j]=max(v[i-1][j],v[i][j-1]); } } } return v[m][n];}bool g(string x,string y){ if(x.size() != y.size()){ return false; } return f(x+x,y)==y.size();}int main(){ string x,y; cin>>x>>y; cout<<g(x,y)<<endl; return 0;}

21判断1.5 分
f 函数的返回值小于等于 $\min\{n,m\}$ 。（）

阅读程序共 1.5 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

22判断1.5 分
f 函数的返回值等于两个输入字符串的最长公共子串的长度。（）

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

（编辑距离）给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace），一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int min(int x, int y, int z) {
    return min(min(x, y), z);
}
int edit_dist_dp(string str1, string str2) {
    int m = str1.length();
    int n = str2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0)
                dp[i][j] = ①;
            else if (j == 0)
                dp[i][j] = ②;
            else if (③)
                dp[i][j] = ④;
            else
                dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], ⑤);
        }
    }
    return dp[m][n];
}
int main() {
    string str1, str2;
    cin >> str1 >> str2;
    cout << "Minimum number of operations: " << edit_dist_dp(str1, str2) << endl;
    return 0;
}

程序

#include <iostream>#include <string>#include <vector>using namespace std;int min(int x, int y, int z) { return min(min(x, y), z);}int edit_dist_dp(string str1, string str2) { int m = str1.length(); int n = str2.length(); vector<vector<int>> dp(m + 1, vector<int>(n + 1)); for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0) dp[i][j] = ①; else if (j == 0) dp[i][j] = ②; else if (③) dp[i][j] = ④; else dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], ⑤); } } return dp[m][n];}int main() { string str1, str2; cin >> str1 >> str2; cout << "Minimum number of operations: " << edit_dist_dp(str1, str2) << endl; return 0;}

38（①）单选空位 ①3 分
①处应填（）

A
j

B
i

C
m

D
n

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

（编辑距离）给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace），一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int min(int x, int y, int z) {
    return min(min(x, y), z);
}
int edit_dist_dp(string str1, string str2) {
    int m = str1.length();
    int n = str2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0)
                dp[i][j] = ①;
            else if (j == 0)
                dp[i][j] = ②;
            else if (③)
                dp[i][j] = ④;
            else
                dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], ⑤);
        }
    }
    return dp[m][n];
}
int main() {
    string str1, str2;
    cin >> str1 >> str2;
    cout << "Minimum number of operations: " << edit_dist_dp(str1, str2) << endl;
    return 0;
}

程序

39（②）单选空位 ②3 分
②处应填（）

A
j

B
i

C
m

D
n

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

（编辑距离）给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace），一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int min(int x, int y, int z) {
    return min(min(x, y), z);
}
int edit_dist_dp(string str1, string str2) {
    int m = str1.length();
    int n = str2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0)
                dp[i][j] = ①;
            else if (j == 0)
                dp[i][j] = ②;
            else if (③)
                dp[i][j] = ④;
            else
                dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], ⑤);
        }
    }
    return dp[m][n];
}
int main() {
    string str1, str2;
    cin >> str1 >> str2;
    cout << "Minimum number of operations: " << edit_dist_dp(str1, str2) << endl;
    return 0;
}

程序

40（③）单选空位 ③3 分
③处应填（）

A
str1[i-1]==str2[j-1]

B
str1[i]==str2[j]

C
str1[i-1]!=str2[j-1]

D
str1[i]!=str2[j]

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

（编辑距离）给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace），一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int min(int x, int y, int z) {
    return min(min(x, y), z);
}
int edit_dist_dp(string str1, string str2) {
    int m = str1.length();
    int n = str2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0)
                dp[i][j] = ①;
            else if (j == 0)
                dp[i][j] = ②;
            else if (③)
                dp[i][j] = ④;
            else
                dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], ⑤);
        }
    }
    return dp[m][n];
}
int main() {
    string str1, str2;
    cin >> str1 >> str2;
    cout << "Minimum number of operations: " << edit_dist_dp(str1, str2) << endl;
    return 0;
}

程序

41（④）单选空位 ④3 分
④处应填（）

A
dp[i-1][j-1]+1

B
dp[i-1][j-1]

C
dp[i-1][j]

D
dp[i][j-1]

完善程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

（编辑距离）给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace），一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int min(int x, int y, int z) {
    return min(min(x, y), z);
}
int edit_dist_dp(string str1, string str2) {
    int m = str1.length();
    int n = str2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0)
                dp[i][j] = ①;
            else if (j == 0)
                dp[i][j] = ②;
            else if (③)
                dp[i][j] = ④;
            else
                dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], ⑤);
        }
    }
    return dp[m][n];
}
int main() {
    string str1, str2;
    cin >> str1 >> str2;
    cout << "Minimum number of operations: " << edit_dist_dp(str1, str2) << endl;
    return 0;
}

程序

42（⑤）单选空位 ⑤3 分
⑤处应填（）

A
dp[i][j] + 1

B
dp[i-1][j-1]+1

C
dp[i-1][j-1]

D
dp[i][j]

阅读程序共 1.5 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

原卷作答说明：判断题正确填 √，错误填 ×

程序

#include <iostream>#include <vector>using namespace std;int compute(vector<int>& cost) { int n = cost.size(); vector<int> dp(n+1, 0); dp[1] = cost[0]; for (int i = 2; i <= n; i++) { dp[i] = min(dp[i-1], dp[i-2]) + cost[i-1]; } return min(dp[n], dp[n-1]);}int main() { int n; cin >> n; vector<int> cost(n); for (int i = 0; i < n; i++) { cin >> cost[i]; } cout << compute(cost) << endl; return 0;}

21判断1.5 分
当输入的 cost 数组为 $\{10, 15, 20\}$ 时，程序的输出为 $15$ 。（）

阅读程序共 2 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

原卷作答说明：判断题正确填 √，错误填 ×

程序

23判断2 分
（2 分）程序总是输出 cost 数组中最小的元素。（）

阅读程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

24单选3 分
单选题
1. 当输入的 cost 数组为 $\{1, 100, 1, 1, 1, 100, 1, 1, 100, 1\}$ 时，程序的输出为（）。
A
6

B
7

C
8

D
9

阅读程序共 4 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

25单选4 分
（4 分）如果输入的 cost 数组为 $\{10, 15, 30, 5, 5, 10, 20\}$ ，程序的输出为（）。

A
25

B
30

C
35

D
40

阅读程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

26单选3 分
若将代码中的 min(dp[i-1], dp[i-2]) + cost[i-1] 修改为 dp[i-1] + cost[i-2]，输入 cost 数组为 $\{5, 10, 15\}$ 时，程序的输出为（）。

A
10

B
15

C
20

D
25

编程题

小木棍

C++时间 1 s内存 512 MB 文件 IO：sticks.in → sticks.out

小 S 喜欢收集小木棍。在收集了 $n$ 根长度相等的小木棍之后，他闲来无事，便用它们拼起了数字。用小木棍拼每种数字的方法如下图所示。

每种数字的小木棍拼法

现在小 S 希望拼出一个正整数，满足如下条件：

拼出这个数恰好使用 $n$ 根小木棍；
拼出的数没有前导 $0$ ；
在满足以上两个条件的前提下，这个数尽可能小。

小 S 想知道这个数是多少，可 $n$ 很大，把木棍整理清楚就把小 S 折腾坏了，所以你需要帮他解决这个问题。如果不存在正整数满足以上条件，你需要输出 $-1$ 进行报告。

输入格式

从文件 sticks.in 中读入数据。

本题有多组测试数据。

输入的第一行包含一个正整数 $T$ ，表示数据组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

一行包含一个整数 $n$ ，表示木棍数。

输出格式

输出到文件 sticks.out 中。

对于每组数据：输出一行，如果存在满足题意的正整数，输出这个数；否则输出 $-1$ 。

样例

输入 1

输出 1

对于第一组测试数据，不存在任何一个正整数可以使用恰好一根小木棍摆出，故输出 $-1$ 。
对于第四组测试数据，注意 $0$ 并不是一个满足要求的方案。摆出 $9$ 、 $41$ 以及 $111$ 都恰好需要 $6$ 根小木棍，但它们不是摆出的数最小的方案。
对于第五组测试数据，摆出 $208$ 需要 $5 + 6 + 7 = 18$ 根小木棍。可以证明摆出任何一个小于 $208$ 的正整数需要的小木棍数都不是 $18$ 。注意尽管拼出 $006$ 也需要 $18$ 根小木棍，但因为这个数有前导零，因此并不是一个满足要求的方案。

数据范围

对于所有测试数据，保证： $1 \le T \le 50$ ， $1 \le n \le 10^5$ 。

测试点编号	$n \le$	特殊性质
$1$	$20$	无
$2$	$50$	无
$3$	$10^3$	A
$4, 5$	$10^5$	A
$6$	$10^3$	B
$7, 8$	$10^5$	B
$9$	$10^3$	无
$10$	$10^5$	无

特殊性质 A：保证 $n$ 是 $7$ 的倍数且 $n \ge 100$ 。

特殊性质 B：保证存在整数 $k$ 使得 $n = 7k + 1$ ，且 $n \ge 100$ 。

部分分

10 分
测试点 $1$ ： $n \le 20$ ，无特殊性质。
10 分
测试点 $2$ ： $n \le 50$ ，无特殊性质。
10 分
测试点 $3$ ： $n \le 10^3$ ，特殊性质 A。
20 分
测试点 $4, 5$ ： $n \le 10^5$ ，无特殊性质。
10 分
测试点 $6$ ： $n \le 10^3$ ，特殊性质 B。
20 分
测试点 $7, 8$ ： $n \le 10^5$ ，无特殊性质。
10 分
测试点 $9$ ： $n \le 10^3$ ，无特殊性质。
10 分
测试点 $10$ ： $n \le 10^5$ ，无特殊性质。

你的代码（C++）

提交后由评测机编译运行，结果见下方

编辑器加载中…

76 B / 64 KB

判题结果

阅读程序共 1.5 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

原卷作答说明：判断题正确填 A，错误填 B

程序

#include <algorithm>#include <cstdio>#include <cstring>#define ll long longint n, k;int a[200007];int ans[200007];int main() { scanf("%d%d", &n, &k); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); } std::sort(a + 1, a + n + 1); n = std::unique(a + 1, a + n + 1) - a - 1; for (int i = 1, j = 0; i <= n; ++i) { for (; j < i && a[i] - a[j + 1] > k; ++j) ; ans[i] = ans[j] + 1; } printf("%d\n", ans[n]); return 0;}

22判断1.5 分
当输入为 3 1 3 2 1 时，输出结果为 $2$ 。（）

阅读程序共 1.5 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

原卷作答说明：判断题正确填 A，错误填 B

程序

23判断1.5 分
假设输入的 $n$ 为正整数，输出的答案一定小于等于 $n$ ，大于等于 $1$ 。（）

阅读程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

25单选3 分
假设输入的 $a$ 数组和 $k$ 均为正整数，执行第 18 行代码时，一定满足的条件不包括（）。

A
$j < i$

B
$a[i] - a[j] > k$

C
$j < n$

D
$a[j] < a[i]$

阅读程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

26单选3 分
当输入的 $n=100$ 、 $k=2$ 、 $a = \{1, 2, \dots, 100\}$ 时，输出为（）。

A
$34$

B
$100$

C
$50$

D
$33$

阅读程序共 1.5 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

原卷作答说明：判断题正确填 A，错误填 B

程序

#include <algorithm>#include <cstdio>#include <cstring>#define ll long longint f[5007][5007];int a[5007], b[5007];int n;int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); } for (int i = 1; i <= n; ++i) { scanf("%d", &b[i]); } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { f[i][j] = std::max(f[i][j], std::max(f[i - 1][j], f[i][j - 1])); if (a[i] == b[j]) { f[i][j] = std::max(f[i][j], f[i - 1][j - 1] + 1); } } } printf("%d\n", f[n][n]); return 0;}

28判断1.5 分
当输入 4 1 2 3 4 1 3 2 2 时，输出为 2。（）

阅读程序共 1.5 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

原卷作答说明：判断题正确填 A，错误填 B

程序

29判断1.5 分
当程序运行完毕后，对于所有的 $1 \leq i, j \leq n$ ，都一定有 $f[i][j] \leq f[n][n]$ 。（）

阅读程序共 1.5 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

原卷作答说明：判断题正确填 A，错误填 B

程序

30判断1.5 分
将第 18 行的 f[i][j] = std::max(f[i][j], std::max(f[i-1][j], f[i][j-1])); 删去后，并不影响程序运行结果。（）

阅读程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

31单选3 分
输出的答案满足的性质有（）。

A
小于等于 $n$

B
大于等于 $0$

C
不一定大于等于 $1$

D
以上均是

阅读程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

32单选3 分
如果在 16 行的循环前加上以下两行：
```
std::sort(a+1, a+n+1);
std::sort(b+1, b+n+1);
```
则答案会（）。
A
变大或不变

B
变小或不变

C
一定变大

D
不变

阅读程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

33单选3 分
如果输入的 $a = \{1, 2, \dots, n\}$ ，而且 $b$ 数组中数字均为 $1 \sim n$ 中的正整数，则上述代码等价于下面哪个问题：（）。

A
求 $b$ 数组去重后的长度

B
求 $b$ 数组的最长上升子序列

C
求 $b$ 数组的长度

D
求 $b$ 数组的最大值

动态规划基础与一维动态规划