IPL匹配中的最大和

Question

在2025年IPL中，每个玩家的支付金额因比赛而异。比赛费用取决于对手的素质、场地等。新赛季每一场比赛的比赛费用都已提前公布。每支球队都必须强制执行轮换政策，这样在本赛季内任何球员都不会连续踢三场比赛。尼基尔是队长，为每一场比赛挑选球队。他想为自己分配一个比赛时间表，以便通过本赛季的比赛费用使他的收入最大化。

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]

其中dpi，1是指在输入数组中播放“i”匹配时可以获得的最高费用。

dpi，0表示在输入数组中不玩“i”匹配时可以获得的最高费用。

Answer 1

第一个简单的想法是找到数组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]

为您的问题编写的代码

#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 2

您的解决方案是错误的，万一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 3

您可以很容易地使用1-DDP让: dpi = sum来处理这个问题，在索引I之前不取3个连续的元素。

从基本案例开始：

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

至于第三个因素，我们将有3个案件：

1-丢弃第3元素

dp[2] = d[1];

2-丢弃第二要素：

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

3-丢弃第一要素：

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

因此，最终的Dp2将是以下3项中的最高值：

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

对于ith元素，我们可以扩展相同的方法：

  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]);