背包DP求解Kattis Roller Coaster Fun问题WA排查求助

数据老陈

2026-8-28

问题背景

我近期刚开始学习动态规划（Dynamic Programming, DP），目前在求解Kattis平台上的「Roller Coaster Fun」题目时遇到障碍：提交后仅通过10/30个测试用例，第11个测试用例返回错误答案，始终未定位到代码逻辑问题。
我的解题思路参考了CPH教材7.1节介绍的硬币问题模型：对上限25000的每个时间点，基于之前时间点的计算结果递推得到最优解，思路伪代码如下：

// fun[i] 表示时间点i能获得的最大乐趣值
// k[i][j] 表示时间点i时，Jimmy乘坐第j个过山车的次数
// 其余函数、变量定义与题目描述一致

fun[1] = 0
fun[n] = max(fun[n - 1], // 继承上一个时间点的结果（不乘坐任何新游乐设施）
             fun[n - t[0]] + f(0, k[n][0]),
             ..., 
             fun[n - t[i]] + f(i, k[n][i]), 
             ..., 
             fun[n - t[N - 1]] + f(N - 1, k[n][N - 1]))

我的完整实现代码如下：

#include <bits/stdc++.h>
using namespace std;

#define MAX_N 100
#define MAX_T 25000

vector<int> a(MAX_N), b(MAX_N), t(MAX_N);

vector<int> dp(MAX_T + 1);
vector<vector<int>> k(MAX_T + 1, vector<int>(MAX_N));

int f(int time, int i)
{
  return max(0, a[i] - k[time][i] * k[time][i] * b[i]);
}

int main()
{
  int N;
  cin >> N;

  for (int i = 0; i < N; ++i)
    cin >> a[i] >> b[i] >> t[i];

  dp[0] = 0;
  fill(k[0].begin(), k[0].end(), 0);

  for (int time = 1; time <= MAX_T; ++time)
  {
    dp[time] = dp[time - 1];
    k[time] = k[time - 1];
    for (int i = 0; i < N; ++i)
    {
      if (time - t[i] >= 0)
      {
        int newFun = dp[time - t[i]] + f(time - t[i], i);
        if (newFun > dp[time])
        {
          dp[time] = newFun;

          k[time] = k[time - t[i]];
          ++k[time][i]; // 多乘坐一次该过山车
        }
      }
    }
  }

  int Q;
  cin >> Q;

  int q;
  for (int i = 0; i < Q; ++i)
  {
    cin >> q;
    cout << dp[q] << '\n';
  }

  return 0;
}

恳请各位帮忙指出思路或代码中存在的问题，不胜感激。

错误分析

你的代码核心问题是状态设计和转移逻辑不匹配，直接照搬了无界背包（硬币问题）的写法，但忽略了题目本身的收益特性：

硬币问题中每种硬币的价值是固定的，属于无界背包模型，可以通过顺序遍历容量+单维度dp数组完成转移。但本题中同一个过山车每多坐一次，获得的乐趣是严格递减的：第1次乘坐收益为a[i]，第2次为a[i]-b[i]，第3次为a[i]-4b[i]，直到收益降到0后再乘坐没有任何正收益，本质上每个过山车的有效乘坐次数是有限的，不满足无界背包的适用条件。
你额外维护的k[time]数组存在状态选择缺陷：当多个转移路径能得到相同的dp[time]值时，你只会选择其中一条路径的乘坐次数记录下来，但这条路径不一定能给后续时间点的转移带来最大收益，会直接导致后续计算结果偏小。举个简单例子：时间点t选择坐过山车A和坐过山车B能拿到一样的乐趣值，但后续时间点坐B的剩余递减收益远高于A，你如果记录了坐A的次数，后续计算的结果就会出错。
每个时间点都拷贝长度为100的k数组虽然不会直接导致错误，但属于完全不必要的内存和时间开销。

修正方案

不需要额外维护乘坐次数数组，分情况把过山车转化为背包物品即可：

对每个过山车i分两类处理：
- 如果b[i] == 0：该过山车每次乘坐收益固定为a[i]，不会递减，按完全背包物品处理
- 如果b[i] > 0：枚举乘坐次数c，直到第c次乘坐的收益小于等于0就停止枚举（坐了也不加乐趣，纯浪费时间），每一次乘坐对应一个单独的01背包物品：花费时间为t[i]，收益为max(0, a[i] - (c-1)*(c-1)*b[i])
对完全背包物品顺序遍历容量转移，对01背包物品倒序遍历容量转移
最后做一次前缀最大值处理，保证dp[i]存储的是时间不超过i时能拿到的最大乐趣（对应原逻辑里继承前一个时间点结果的操作）

这个方案的时间复杂度完全符合要求：100个过山车每个最多拆分出约30个有效物品（因为sqrt(1000/1)≈32），总物品数约3000，配合25000的背包容量，总计算量不到1e8，完全可以在时限内跑完。
核心实现参考：

vector<int> dp(MAX_T + 1, 0);
for (int i = 0; i < N; ++i) {
    if (b[i] == 0) {
        // 收益不递减，按完全背包处理
        int val = a[i];
        int cost = t[i];
        for (int j = cost; j <= MAX_T; ++j) {
            dp[j] = max(dp[j], dp[j - cost] + val);
        }
    } else {
        // 收益递减，拆分多次乘坐为01物品
        for (int c = 1; ; ++c) {
            int val = a[i] - (c-1)*(c-1)*b[i];
            if (val <= 0) break;
            int cost = t[i];
            for (int j = MAX_T; j >= cost; --j) {
                dp[j] = max(dp[j], dp[j - cost] + val);
            }
        }
    }
}
// 处理时间剩余的情况：时间i的最优解至少和时间i-1一样好
for (int i = 1; i <= MAX_T; ++i) {
    dp[i] = max(dp[i], dp[i-1]);
}

内容的提问来源于stack exchange，提问作者Ayush Garg