c++ - Spoj上的Farida公主

我陷入问题SPOJ。
我检查了所有通过的测试用例，但是我仍然在spoj上收到“WA”。
我知道可以使用动态编程来解决，但是我正在练习记忆。

这是我的代码:

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



测试案例2:



输出1:



输出2:

最佳答案

您使用错误的数据类型将值存储在 vector dp中。
由于硬币的总和可以达到(10 ^ 9 * 10 ^ 2 = 10 ^ 11)，因此int无法存储它。请尝试使用long long int代替，因为这不会导致溢出情况。
与您相同的代码(使用long long int被接受):
使用:vector 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();


}
}

关于c++ - Spoj上的Farida公主，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/54143593/