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 [1,1]是指可以得到时的最高费用玩'我'在输入数组匹配。

和dp [i，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] 

有关问题的代码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; 
} 

如果你想一点点，你就能optimaze代码。

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所有比赛到我，不只是一个匹配，因此增加两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])