C/C++编程六级 题库
共 4 道题
· 按题型筛选,点「查看答案」核对解析
1
单选题
适中
完全背包和01背包的核心区别是?( )
A
完全背包的物品数量更多
B
完全背包的每件物品可以选择无限次,01背包只能选一次
C
完全背包的背包容量更大
D
完全背包只能用二维DP数组实现
答案与解析
正确答案:B
完全背包与01背包的机制差异体现在物品选择次数上。在状态转移过程中,每件物品是否可被重复选取直接影响决策逻辑。若允许对同一件物品多次选取,则当前阶段的状态可由同一物品在之前阶段更新后的状态再次推导;若仅允许选取一次,则当前物品对每个状态最多贡献一次影响。该差异导致两者在动态规划数组更新顺序上的不同:前者可在一次遍历中正序更新以允许多次选取,后者需逆序更新以避免重复使用同一物品。实现维度与物品总数、背包容量等参数无必然关联,二维数组可用于任一模型,非二者本质区别特征。
2
单选题
适中
01背包问题中,一维DP数组的内层循环需要逆序遍历,其原因?( )
A
降低时间复杂度
B
避免同一件物品被多次选择
C
减少空间使用
D
提高代码可读性
答案与解析
正确答案:B
这道题暂未补解析。
3
简答题
偏难
古董
拍卖师准备了 N 件古董进行拍卖。这些古董有以下重要特性:
陈列规则:所有古董按 1、……、N 编号陈列在一条长廊中,每天拍卖师只能从长廊任一端取出一件古董拍卖。
升值效应:古董拍卖顺序直接影响成交价。若第 i 件古董在第 a天拍卖,成交价为 Vi×a(Vi 为初始估价)。
价值分布:第 i 件古董的初始估价 Vi 取决于其陈列位置——从入口端开始,第 i 个展柜内的古董估价为Vi。
拍卖师需要制定最优拍卖顺序,最大化总成交额。请帮助他计算出古董全部售出后的最大收益。
时间限制:1000ms内存限制:256MB
输入格式
第一行:古董数量 N;
接下来 n 行:古董初始估价序列 V1~VN;
输出格式
一行整数,表示最大总收益。
输入样例
5 1 3 1 5 2
输出样例
43
数据范围:
1≤N≤2000,1≤Vi≤1000。
答案与解析
参考答案
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 2005;
int dp[MAXN][MAXN];
int V[MAXN];
int main() {
int N;
cin >> N;
for (int i = 1; i <= N; ++i) {
cin >> V[i];
}
// 初始化长度为1的子序列(只剩一件古董时)
for (int i = 1; i <= N; ++i) {
dp[i][i] = V[i] * N;
}
// 处理长度为l的子序列(l从2到N)
for (int l = 2; l <= N; ++l) {
for (int i = 1; i + l - 1 <= N; ++i) {
int j = i + l - 1; // 子序列的右端点
int k = N - l + 1; // 当前拍卖的天数
// 取左端或右端,选择收益更大的方案
dp[i][j] = max(V[i] * k + dp[i + 1][j], V[j] * k + dp[i][j - 1]);
}
}
cout << dp[1][N] << endl;
return 0;
}//参考代码2
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
// dp[i][j] 表示从第i件到第j件古董能获得的最大收益
vector<vector<long long>> dp(n, vector<long long>(n, 0));
// 初始化:单件古董在第n天拍卖(最后一天)
for (int i = 0; i < n; i++) {
dp[i][i] = (long long)v[i] * n;
}
// 区间DP:从小区间到大区间
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
int day = n - len + 1; // 当前拍卖的天数
// 选择左端古董:v[i] * day + dp[i+1][j]
// 选择右端古董:v[j] * day + dp[i][j-1]
dp[i][j] = max((long long)v[i] * day + dp[i+1][j],
(long long)v[j] * day + dp[i][j-1]);
}
}
cout << dp[0][n-1] << endl;
return 0;
}
4
简答题
偏难
搬运水果
在果园里,n 堆果实排成一个环形,第 i 堆果实的重量为 ai。果农需要将所有果实合并成一堆。合并规则如下:
(1)每次只能合并相邻的两堆,新堆的重量为两堆重量之和;
(2)每次合并消耗的体力等于新堆的重量;
(3)合并后新堆与剩余堆仍保持环形排列。
请设计合并顺序,求出合并全过程消耗的最小总体力与最大总体力。
时间限制:1000ms内存限制:256MB
输入格式
第一行:整数 n,表示果实堆数;
第二行:n 个整数 a1、a2、……、an,表示每堆果实的重量。
输出格式
第一行:最小总体力消耗;
第二行:最大总体力消耗。
输入样例
4 4 5 9 4
输出样例
43 54
数据范围:
1≤n≤100,1≤ai≤1000。
答案与解析
参考答案
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(2 * n + 1, 0);
vector<int> prefix(2 * n + 1, 0);
// 读取输入并构建环形数组(复制一份接在末尾)
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i + n] = a[i];
}
// 计算前缀和
for (int i = 1; i <= 2 * n; i++) {
prefix[i] = prefix[i - 1] + a[i];
}
// DP数组初始化
vector<vector<int>> dp_min(2 * n + 1, vector<int>(2 * n + 1, INT_MAX));
vector<vector<int>> dp_max(2 * n + 1, vector<int>(2 * n + 1, 0));
// 初始化单个区间
for (int i = 1; i <= 2 * n; i++) {
dp_min[i][i] = 0;
dp_max[i][i] = 0;
}
// 区间DP计算
for (int len = 2; len <= n; len++) { // 区间长度
for (int l = 1; l <= 2 * n - len + 1; l++) { // 左端点
int r = l + len - 1; // 右端点
for (int k = l; k < r; k++) { // 分割点
int sum = prefix[r] - prefix[l - 1];
dp_min[l][r] = min(dp_min[l][r], dp_min[l][k] + dp_min[k + 1][r] + sum);
dp_max[l][r] = max(dp_max[l][r], dp_max[l][k] + dp_max[k + 1][r] + sum);
}
}
}
// 在环形中找最小值和最大值
int min_cost = INT_MAX;
int max_cost = 0;
for (int i = 1; i <= n; i++) {
min_cost = min(min_cost, dp_min[i][i + n - 1]);
max_cost = max(max_cost, dp_max[i][i + n - 1]);
}
cout << min_cost << endl;
cout << max_cost << endl;
return 0;
}//参考代码2
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
const int INF = INT_MAX / 2; // 避免溢出
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
if (n == 1) { // 只有一堆,无需合并
cout << 0 << endl;
cout << 0 << endl;
return 0;
}
// 将环形转为线性,扩展数组为2n长度
vector<int> b(2 * n);
for (int i = 0; i < 2 * n; ++i) {
b[i] = a[i % n];
}
// 计算前缀和,s[0] = 0, s[i] = b[0] + ... + b[i-1]
vector<int> s(2 * n + 1, 0);
for (int i = 1; i <= 2 * n; ++i) {
s[i] = s[i - 1] + b[i - 1];
}
// 初始化动态规划数组
vector<vector<int>> min_dp(2 * n, vector<int>(2 * n, 0));
vector<vector<int>> max_dp(2 * n, vector<int>(2 * n, 0));
// 填充dp数组,l为合并的堆数(从2到n)
for (int l = 2; l <= n; ++l) { // l表示当前合并的堆数
for (int i = 0; i + l - 1 < 2 * n; ++i) { // i为起始位置
int j = i + l - 1; // j为结束位置
// 初始化当前区间的最小和最大值
min_dp[i][j] = INF;
max_dp[i][j] = 0;
int sum_ij = s[j + 1] - s[i]; // i到j的总重量
// 尝试所有可能的拆分点k
for (int k = i; k < j; ++k) {
// 更新最小值
min_dp[i][j] = min(min_dp[i][j], min_dp[i][k] + min_dp[k + 1][j] + sum_ij);
// 更新最大值
max_dp[i][j] = max(max_dp[i][j], max_dp[i][k] + max_dp[k + 1][j] + sum_ij);
}
}
}
// 寻找环形结构的最小和最大体力消耗(所有可能的起始位置)
int min_total = INF;
int max_total = 0;
for (int i = 0; i < n; ++i) {
min_total = min(min_total, min_dp[i][i + n - 1]);
max_total = max(max_total, max_dp[i][i + n - 1]);
}
cout << min_total << endl;
cout << max_total << endl;
return 0;
}