CSES动态规划问题Book Shop及Coin Combination 2出现TLE求助

超时原因分析 #

• 输入输出效率低下：默认启用同步的cin/cout处理大数据量时速度极慢，这是CSES题目超时的高频诱因。
• DP实现未优化：使用二维DP数组会带来额外内存开销与缓存访问成本，常数时间远高于一维滚动数组；若循环顺序错误（如01背包正序遍历容量），还会引发重复计算，进一步拖慢运行速度。
• 不必要的大数据类型：在结果未超出int范围时使用long long，会增加内存占用与数据读写耗时（但这并非核心超时原因）。

优化方案 #

1. 输入输出加速 #

添加代码关闭cin/cout与C标准库的同步，或直接使用scanf/printf：

ios_base::sync_with_stdio(false);
cin.tie(NULL);

2. DP算法优化 #

• 《Book Shop》（01背包）：采用一维滚动数组，倒序遍历容量（从总预算x到当前书的价格），避免重复选取同一本书，空间复杂度从O(n*x)降至O(x)，大幅减少内存操作开销。
• Coin Combination 2（完全背包变种）：使用一维数组正序遍历容量（因硬币可重复选取），同样压缩空间并降低常数时间。

3. 数据类型精简 #

确认结果范围后，用int替代long long（若题目允许），减少内存访问成本。

优化后的《Book Shop》代码示例 #

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, x;
    cin >> n >> x;
    vector<int> price(n), pages(n);
    for (int i = 0; i < n; ++i) {
        cin >> price[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> pages[i];
    }
    
    vector<int> dp(x + 1, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = x; j >= price[i]; --j) {
            dp[j] = max(dp[j], dp[j - price[i]] + pages[i]);
        }
    }
    cout << dp[x] << endl;
    return 0;
}

内容的提问来源于stack exchange，提问作者Aarushi Agarwal