能给个思路吗，实在做不出来/(ㄒoㄒ)/~~

Question

能给个C++的思路吗？谢谢
题目描述

A 一共购买了n本书，第i本书的吸引力是k_i。可多按照吸引力从左到右单调不减（ki>=ki-1)的方式，将所有书放在了书架上。
A一共花费t分钟阅读。
对于每一本书，他可以花费 a 分钟完整阅读，也可以花费 b 分钟，只通过封面了解内容。
A将从最左侧的第一本书籍开始阅读，当他读完当前的书后（完整阅读或通过目录了解内容），他开始阅读紧靠右侧的下一本书。A的灵感值与他完整阅读的书的吸引力之和相等。
注意：如果A开始阅读一本书，但是没有在第 t 分钟结束前读完，这本书将不会对可多的灵感值产生贡献。

输入描述

输入的第一行包含四个整数 n,t,a,b（1≤n≤2⋅10^5 ，1≤t≤10^9 ，1≤b<a≤10^9 ）分别表示书的数目，可多阅读的时间，完整阅读和阅读封面所需要的时间。
第二行包含n个整数ki（1≤ki≤10^9 ，ki≤ki+1 ），表示书的吸引力。

输出描述

输出一行一个整数，表示 t 分钟后A灵感最大值。

样例1

输入

3 5 2 1
2 2 4

输出

6

Answer 1

引自免费微信小程序：皆我百晓生

为了解决这个问题，我们可以通过动态规划的方法来找到在时间限制内可以获得的最大灵感值。关键在于决定每本书是否值得花费更多时间去完整阅读，还是仅通过封面了解内容。

思路解析

1. 初始化变量：

   • n：书籍总数
   • t：总阅读时间
   • a：完整阅读一本书所需时间
   • b：通过封面了解内容所需时间
   • k：吸引力数组

2. 动态规划定义：

   • 定义状态 dp[i] 表示在阅读到第 i 本书时，可以获得的最大灵感值。

3. 状态转移方程：

   • 对于每一本书，有两种选择：
     • 通过封面了解内容：dp[i] = dp[i-1] + 0 （因为封面阅读不增加灵感值）
     • 完整阅读：查找之前的状态 j 使得从 j 到 i 的所有书都可以在剩余时间内完整阅读，更新 dp[i]。

4. 边界条件：

   • dp[0] = 0，初始时没有阅读任何书。

5. 计算过程：

   • 使用两个指针 left 和 right 来追踪可能的完整阅读区间。
   • 更新 dp[i] 时，检查从 left 到 i 的所有书是否能在剩余时间内完整阅读，如果不能，则向前移动 left 指针。
   • 计算 dp[i] 的值时，取 dp[i-1] 和从 left 到 i 完整阅读获得的灵感值的最大值。

示例代码

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, t, a, b;
    cin >> n >> t >> a >> b;
    
    vector<int> k(n);
    for (int i = 0; i < n; ++i) {
        cin >> k[i];
    }
    
    vector<int> dp(n + 1, 0);
    int left = 0, cost = 0;
    
    for (int i = 1; i <= n; ++i) {
        // 更新成本
        while (cost + a <= t && left < i) {
            cost += a;
            left++;
        }
        
        // 当前书完整阅读的成本
        int currentCost = (i - left) * a - (cost - (i - left - 1) * b);
        
        // 如果当前书不能在剩余时间内完整阅读，则向前移动left指针
        while (currentCost > t - cost + (i - left) * b) {
            cost -= a;
            left--;
            currentCost = (i - left) * a - (cost - (i - left - 1) * b);
        }
        
        // 状态转移
        dp[i] = max(dp[i-1], dp[left] + k[i-1]);
    }
    
    cout << dp[n] << endl;
    
    return 0;
}

注意事项

• 这段代码在处理状态转移时，考虑了两种情况：封面阅读和完整阅读，但简化了部分逻辑以提高效率。
• 确保输入数据的正确性，并考虑到边界条件和溢出问题。
• 动态规划数组的大小应适当调整，以防超出内存限制。

通过上述方法，我们可以有效地解决题目中的问题，找到在给定时间内可以获得的最大灵感值。