algorithm - DP 问题 (IPL) 未通过 2 个测试用例

问题描述

这是 IPL 的问题：http ://www.iarcs.org.in/inoi/2014/zco2014/zco2014-2b.php

在 IPL 2025 中，每位玩家获得的金额因比赛而异。比赛费用取决于对手的质量、场地等。

新赛季每场比赛的比赛费用已经提前公布。每支球队都必须执行强制性轮换政策，以确保没有球员在赛季中连续打三场比赛。

Nikhil 是队长并为每场比赛选择球队。他想为自己分配一个比赛时间表，以通过赛季期间的比赛费用来最大化他的收入。

输入格式

第 1 行：单个整数 N，IPL 赛季的比赛场数。

第 2 行：N 个非负整数，其中位置 i 的整数表示匹配 i 的费用。

输出格式

输出由一个非负整数组成，即 Nikhil 在此 IPL 赛季中可以赚取的最大金额。

测试数据

只有一个子任务值 100 分。在所有输入中：

1≤N≤2×10^5

每场比赛的费用在0到10^4之间，包括在内。

实时评估数据

考试期间服务器上有 12 个测试输入。

限制

时间限制：1s

内存限制：32 MB

我已经在代码本身中包含了我对 DP 的所有逻辑，所以我没有单独提及逻辑。10 个测试用例正确通过，而其余 2 个测试用例（第二个和介于两者之间）显示 WA，尽管我认为逻辑很好。也许我错过了一些边缘案例/基本案例。

这是下面的代码（Ideone 链接：https ://ideone.com/pPZFPJ ）

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N; cin>>N;
    int arr[N];
    for (int i=0; i<=N-1; i++) cin>>arr[i];

    int dp[N][3];

    // dp[i][0]=max money on day i s.t he charges on day i,i-1
    // dp[i][1]=max money on day i s.t he charges on day i,i-2
    // dp[i][2]=max money on day i s.t he charges on day i,i-3

    dp[0][0] = arr[0]; dp[1][1]=arr[1];
    dp[1][0] = arr[0]+arr[1]; //second day
    dp[2][0] = arr[1]+arr[2]; dp[2][1] = arr[0]+arr[2]; dp[2][2] = 0;

    for (int i=3; i<N; ++i) {
    dp[i][0] = arr[i] + max(dp[i-1][1],dp[i-1][2]);
    dp[i][1] = arr[i] + max(dp[i-2][0],dp[i-2][1]);
    dp[i][2] = arr[i] + dp[i-3][0];
    }

    cout<<max(max(dp[N-1][0],dp[N-1][1]),dp[N-1][2])<<endl;

    /*for (int i=0; i<=N-1; i++)
    {
        for (int j=0; j<=2; ++j)
        cout<<dp[i][j] << "   ";
        cout<<endl;
    }*/
}

/*1 2 3 4 5 6 7 8 9.... i-5 i-4 i-3 i-2 i-1 i i+1 i+2 i+3 ..... N*/

请注意，如果打字的人熟悉其他语言，请用 C、C++、Java 之间的代码编写代码，否则我可能很难理解。伪代码对我来说同样适用，但请说明基本情况。另外，我不希望改变 DP 的逻辑，因为我知道 2 个更简单的 DP 解决方案（并且它们已经正确通过）。

标签： algorithmc++14dynamic-programming

algorithm - DP 问题 (IPL) 未通过 2 个测试用例

问题描述

解决方案

推荐阅读