Принцесса Фарида на Спой
Я застрял на проблеме SPOJ.
Я проверил все тестовые примеры, пройдя все из них, но я все еще получаю "WA" на spoj.
Я знаю, что это можно решить с помощью динамического программирования, но я практикую мемоизацию.
Вот мой код:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector <int> dp(1000000);
long long int maxloot(vector<int> &loot, int n) {
if (n == 0)
return 0;
if (n == 1)
return loot[0];
if (n == 2)
return max(loot[0], loot[1]);
if (dp[n] != -1)
return dp[n];
long long int take = loot[n - 1] + maxloot(loot, n - 2);
long long int leave = maxloot(loot, n - 1);
return dp[n]= max(take, leave);
}
int main() {
int t;
cin >> t;
int p = 1;
while (t--) {
int n;
cin >> n;
vector <int> loot;
for (int i = 0; i < n; i++) {
int temp;
cin >> temp;
loot.push_back(temp);
}
dp.assign(1000000, -1);
cout <<"Case "<<p<<": "<< maxloot(loot, n)<<endl;
p++;
dp.clear();
}
}
Тестовый пример 1:
5
1 2 3 4 5
Тестовый пример 2:
1
10
вывод 1:
9
вывод 2:
10
ах, вы имеете в виду, что проходите все тестовые примеры, но не скрытые. В этом случае вам нужно выполнить больше тестовых случаев. Найдите тот, который не проходит, и исправьте его.
Если вы не знаете фактического ввода, действительно невозможно правильно отладить вашу программу.
по моему опыту, невозможно написать код, который будет производить правильный вывод для ввода все. Следовательно, если вы не знаете, какой ввод вызывает неправильный вывод, вы не можете это исправить.
как только я использовал int * int и сохранял значения в long long, в этом случае максимальное значение int было 1000000, что достаточно для int, но int * int переполнилось до того, как результат будет сохранен в течение длительного времени, потому что процессор выполнял все вычисления в int, а затем он долго хранил, когда я добавлю int и long long, это может создать некоторые проблемы? @Someprogrammerdude
ну, это решение явно не будет работать, если есть 10 ^ 4 монстров, и каждый содержит 10 ^ 9 монет (что может случиться по правилам), потому что ваш массив dp содержит только целое число, которое будет переполнено. Не могу сказать, причина ли это в WA.
Вычисления в long long int имеют ограниченное применение, если вы сохраняете результаты в vector<int>.
принято, спасибо @ grungegurunge
Ответы 1
Вы используете неправильный тип данных для хранения значения в векторе dp. Поскольку сумма монет может достигать (10 ^ 9 * 10 ^ 2 = 10 ^ 11), поэтому int не сможет ее сохранить. Попробуйте вместо этого использовать long long int, так как это не приведет к состоянию переполнения.
Тот же код, что и ваш (принято использование long long int):
ИСПОЛЬЗОВАНИЕ: vector <long long int> dp (1000000)
ПРИНЯТЫЙ КОД:
#include<iostream>
#include<vector>
#include<algorithm>
#define ull unsigned long long
using namespace std;
vector <long long int> dp(1000000);
long long int maxloot(vector<int> &loot, int n) {
if (n == 0)
return 0;
if (n == 1)
return loot[0];
if (n == 2)
return max(loot[0], loot[1]);
if (dp[n] != -1)
return dp[n];
long long int take = loot[n - 1] + maxloot(loot, n - 2);
long long int leave = maxloot(loot, n - 1);
return dp[n]= max(take, leave);
}
int main() {
int t;
cin >> t;
int p = 1;
while (t--) {
int n;
cin >> n;
vector <int> loot;
for (int i = 0; i < n; i++) {
int temp;
cin >> temp;
loot.push_back(temp);
}
dp.assign(1000000, -1);
cout <<"Case "<<p<<": "<< maxloot(loot, n)<<endl;
p++;
dp.clear();
}
}
Если вы прошли все тесты, но по-прежнему получаете «неправильный ответ», возможно, у вас что-то не так с выходным форматом. Подобные ситуации - еще одна причина, по которой онлайн-судьи негодяи.