首页 › 题库 › C/C++编程考级 › 4 动态规划

C/C++编程六级 题库

共 4 道题 · 按题型筛选,点「查看答案」核对解析
章节 4 动态规划 清除
1 单选题 适中 C/C++编程考级 ·C/C++编程六级 · 4 动态规划
完全背包和01背包的核心区别是?( )
A
完全背包的物品数量更多
B
完全背包的每件物品可以选择无限次,01背包只能选一次
C
完全背包的背包容量更大
D
完全背包只能用二维DP数组实现
答案与解析
正确答案:B
完全背包与01背包的机制差异体现在物品选择次数上。在状态转移过程中,每件物品是否可被重复选取直接影响决策逻辑。若允许对同一件物品多次选取,则当前阶段的状态可由同一物品在之前阶段更新后的状态再次推导;若仅允许选取一次,则当前物品对每个状态最多贡献一次影响。该差异导致两者在动态规划数组更新顺序上的不同:前者可在一次遍历中正序更新以允许多次选取,后者需逆序更新以避免重复使用同一物品。实现维度与物品总数、背包容量等参数无必然关联,二维数组可用于任一模型,非二者本质区别特征。
题目详情
2 单选题 适中 C/C++编程考级 ·C/C++编程六级 · 4 动态规划

01背包问题中,一维DP数组的内层循环需要逆序遍历,其原因?( )

A
降低时间复杂度
B
避免同一件物品被多次选择
C
减少空间使用
D
提高代码可读性
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
3 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 4 动态规划

古董

拍卖师准备了 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 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 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;
}
题目详情