1 条题解

  • 0
    @ 2026-1-14 20:10:27
    #include<bits/stdc++.h>
    using namespace std;
    
    const int MAXN = 1000010;
    int n;
    struct Application {
        int a, b;
    } apps[MAXN];
    long long dp[MAXN]; // dp[i]表示从第i个申请开始处理能获得的最大收益
    
    int main() {
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> apps[i].a >> apps[i].b;
        }
        
        // 从后往前计算dp
        for (int i = n - 1; i >= 0; i--) {
            // 如果接受当前申请
            int next = i + apps[i].b + 1;
            long long accept = apps[i].a;
            if (next <= n) {
                accept += dp[next];
            }
            
            // 如果拒绝当前申请
            long long reject = dp[i + 1];
            
            // 取两者中的最大值
            dp[i] = max(accept, reject);
        }
        
        cout << dp[0] << endl;
        return 0;
    }
    
    • 1

    信息

    ID
    1452
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者