Вот проблема IPL: http://www.iarcs.org.in/inoi/2014/zco2014/zco2014-2b.php
В IPL 2025 сумма, которую получает каждый игрок, варьируется от матча к матчу.Плата за матч зависит от качества противника, места проведения и т. Д.
Плата за матч за каждый матч в новом сезоне была объявлена заранее.Каждая команда должна применять обязательную политику ротации, чтобы ни один игрок не сыграл три матча подряд в течение сезона.
Никхил является капитаном и выбирает команду для каждого матча.Он хочет выделить для себя график игры, чтобы максимизировать свой заработок за счет сборов за матч в течение сезона.
Формат ввода
Строка 1: одно целое число N, количество игр в сезоне IPL..
Строка 2: N неотрицательных целых чисел, где целое число в позиции i представляет плату за совпадение i.
Формат вывода
Вывод состоит из одного не-отрицательное целое число, максимальная сумма денег, которую Nikhil может заработать в этом сезоне IPL.
Тестовые данные
Существует только одна подзадача стоимостью 100 марок.Во всех входах:
1 ≤ N ≤ 2 × 10 ^ 5
Плата за каждый матч составляет от 0 до 10 ^ 4 включительно.
Данные оценки в реальном времени
Во время экзамена на сервере имеется 12 тестовых входов.
Ограничения
Ограничение по времени: 1 с
Ограничение памяти: 32 МБ
Я включил всю свою логику для DP в сам код, поэтому я не буду отдельно упоминать логику.10 тестов успешно пройдены, в то время как остальные 2 теста (2-й и где-то посередине) показывают WA, хотя я думаю, что логика в порядке.Может быть, есть какой-то крайний случай / базовый случай, который я пропускаю.
Вот код ниже (Идеальная ссылка: 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 (и они прошли правильно).