0

私はこの問題を解決しています - > http://www.spoj.com/problems/COINS/。非常に簡単な DP アプローチを使用した非常に単純な DP 問題です。DP を使用するための問題ステートメントに十分なヒントが見つかりました。すべてのテスト ケースはコンパイラで完全に実行されていますが、SPOJ で WA を取得しています。私のコードは次のとおりです。

私のコード

#include <cstdio>
#include <map>
#include <cstring>
#include<algorithm>
using namespace std;
map< long long,long long > data;
map < long long,long long> :: iterator p;
int max(int a,int b)
{
    if(a>b)return a;
        return b;
}
long long calc(int n)
{
    long long c;
    if(n==0 || n==1 || n==2)
        return n;
p = data.find(n);
 if(p==data.end())
 {
    c = max(n, calc(n/2) + calc(n/3) + calc(n/4));
            data.insert(p, pair < long long, long long > (n, c));
            return c;
 }
else return (*p).second;

}
int main()
{
    int t;
    long long n;
    scanf("%d",&t);
    if(t>10)return 0;
    while(t--)
    {
        scanf("%lld",&n);
        if(n<0 || n>1000000000)
            break;
        data.clear();
        printf("%lld",calc(n));
    }
    return 0;
 }

どこが間違っているのかを理解するのは本当に難しいと思います！

私のコードと矛盾するテストケースでも構いません。

4

4 に答える 4

2

動的プログラミングを使用して、結果を配列に格納します。値は最大 10^9 になる可能性があり、そのサイズの配列を取得することはできないため、10^6 までのサイズの配列を取得し、その結果を保存し、残りの値を単純な再帰を使用して計算します。

于 2013-11-17T11:03:45.657 に答える
2

のスタック オーバーフローの可能性がありcalculateます。再帰はあなたのプログラムを殺しています:-)

calculate(1000000000)または単に遅すぎるという事実。

于 2013-08-12T15:44:47.703 に答える
1

ここにpythonの解決策があります

import sys
mydict = {}
def count(n):
    if n <= 5:
        return n
    elif n in mydict.keys():
        return mydict[n]
    else:
        k=max(n,count(n / 2) + count(n / 3) + count(n / 4))
        mydict[n]=k
        return mydict[n]

for line in sys.stdin:
    res = count(int(line))
    print(int(res))
于 2014-11-08T18:39:01.593 に答える