全部评论 8

  • #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    typedef long long ll;
    
    int main() {
        int N, M, K;
        cin >> N >> M >> K;
        
        vector<int> A(N+1), B(N+1);
        for (int i = 1; i <= N; i++) {
            cin >> A[i] >> B[i];
        }
        
        // dp[j][cost]: 最后一个选择的城镇是 j,总花费为 cost 时的最大利润
        // j=0 表示还没有选择任何城镇
        vector<vector<ll>> dp(N+1, vector<ll>(M+1, -1));
        dp[0][0] = 0;  // 初始状态:没有选择任何城镇,花费0,利润0
        
        for (int i = 1; i <= N; i++) {
            // 新的 dp 数组,用于滚动更新
            vector<vector<ll>> new_dp = dp;
            
            for (int j = 0; j <= N; j++) {
                for (int cost = 0; cost <= M; cost++) {
                    if (dp[j][cost] < 0) continue;  // 无效状态
                    
                    // 情况1:不选第 i 个城镇 - 已经通过 new_dp = dp 复制了
                    
                    // 情况2:选择第 i 个城镇
                    int new_cost = cost + B[i];
                    if (new_cost <= M) {
                        // 如果这是第一个选择的城镇 (j=0)
                        if (j == 0) {
                            new_dp[i][new_cost] = max(new_dp[i][new_cost], dp[j][cost] + A[i]);
                        }
                        // 如果之前有选择的城镇,检查距离约束
                        else if (i - j <= K) {
                            new_dp[i][new_cost] = max(new_dp[i][new_cost], dp[j][cost] + A[i]);
                        }
                    }
                }
            }
            
            dp = move(new_dp);
        }
        
        // 查找所有可能状态中的最大利润
        ll ans = 0;
        for (int j = 0; j <= N; j++) {
            for (int cost = 0; cost <= M; cost++) {
                ans = max(ans, dp[j][cost]);
            }
        }
        
        cout << ans << endl;
        
        return 0;
    }
    

    1周前 来自 浙江

    1
  • h
    hh

    1周前 来自 广东

    0
  • 1周前 来自 浙江

    0
  • 不是AI?

    1周前 来自 北京

    0
  • 6

    1周前 来自 湖北

    0
    • userId_undefined
      CuSn
      回复
      wcqk

      em...

      1周前 来自 浙江

      0
  • 什么是Atcoder?

    1周前 来自 浙江

    0
  • 这次比赛 A 我单手 10 s AC

    1周前 来自 浙江

    0
  • 200分

    1周前 来自 浙江

    0

热门讨论