IPL比赛中的最大总和

Question

在 IPL 2025 中，支付给每个球员的金额因比赛而异。比赛费用取决于对手的质量、场地等。新赛季每场比赛的比赛费用已经提前公布。每支球队都必须执行强制轮换政策，这样就没有球员在赛季中连续参加三场比赛。 Nikhil 是队长，负责为每场比赛选择球队。他想给自己分配一个赛程，在赛季中通过比赛费用最大化收入。

Input: 10 3 5 7 3
Output: 23
(Explanation: 10+3+7+3)
Input: 3 2 3 2 3 5 1 3
Output: 17
(Explanation: 3+3+3+5+3)

我的循环关系如下，我想知道是对还是错：

dp[i, 1] = max(dp[i-1][0] + c[i], dp[i-1][1])

dp[i, 0] = dp[i-1][1] + dp[i-2][1]

其中 dp[i, 1] 表示在输入数组中进行 'i' 场比赛时可以获得的最大费用。

和dp[i, 0]表示在输入数组中不玩'i'比赛时可以获得的最大费用。

Answer 1

你的解决方案是错误的，在 dp[i, 1] 的情况下，你没有考虑玩家玩游戏 i - 1 并跳过游戏 i - 2 的情况，这是一个有效案例。

如果你跳过 ith 匹配，dp[i, 0] = dp[i - 1][1] + dp[i - 2][1] 也是错误的，因为 dp[i, 1] 考虑了从 0 到 i 的所有匹配，而不仅仅是一个匹配，所以添加两个dp[i - 1, 1] 和 dp[i - 1, 2] 将重复计算。

修复：

dp[i, 1] = max(dp[i - 1, 0] + c[i]  , dp[i - 2, 0] + c[i - 1] + c[i])
dp[i, 0] = max(dp[i - 1, 1] , dp[i - 1, 0])

Answer 2

第一个简单的想法是找到数组dp[N][3]。的递归关系：

dp[i][0] = max( dp[i-2][2] ,dp[i-2][1] )
dp[i][1] = max( dp[i-1][0] + A[i], dp[i-2][1] + A[i], dp[i-2][2] + A[i])
dp[i][2] = dp[i-1][1] + A[i]

你的问题的代码bwlow

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include<cstring>
#include <math.h>
#include<cstdio>
#include<string>
#include <queue>
#include <list>

using namespace std;

int dp[100000][3];
int main(){
    int n = 8;
    int A[] ={3,2,3,2,3,5,1,3};
    memset(dp,0,sizeof(dp));
    dp[0][1] = A[0];
    dp[1][1] = max(A[0],A[1]);
    dp[0][2] = A[0];
    dp[1][2] = A[0]+A[1];
    int ans = 0;
    for(int i = 2; i<n; i++){
        dp[i][0] = max(dp[i-2][2],dp[i-2][1]);
        dp[i][1] = max(max(dp[i-1][0]+A[i],dp[i-2][1]+A[i]),dp[i-2][2]+A[i]);
        dp[i][2] = dp[i-1][1]+A[i];
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<3; j++){
            ans = max(ans,dp[i][j]);
        }
    }
    cout<<ans;
    return 0;
}

稍加思考就可以优化代码。

Answer 3

你可以用 1-D DP 轻松解决这个问题让： dp[i] = 不取 3 个连续元素的和直到索引 i .

从基本案例开始：

//taking only first element 
dp[0] = a[0];
//taking first and second element
dp[1] = a[1];

对于第三个元素，我们将有 3 种情况：

1- 丢弃第三个元素

dp[2] = d[1];

2- 丢弃第二个元素：

dp[2] = dp[0] + a[2]

3- 丢弃第一个元素：

dp[2] = a[1] + a[2]

所以最终 Dp[2] 将是这 3 个中的最大值：

dp[2] = max( dp[1] , max( dp[0] + a[2] , a[1] + a[2] ) );

我们可以为第 i 个元素扩展相同的方法：

  dp[i] = dp[i-1];
  dp[i] = max(dp[i],dp[i-2]+a[i]);
  dp[i] = max(dp[i],dp[i-3] + a[i-1]+a[i]);

IPL比赛中的最大总和

maximum sum in IPL matches

algorithm

recursion

dynamic-programming