c - 使用 BigInteger 进行 SPOJ 动态规划 - SETNJA

Question

我试图解决以下 spoj 问题http://www.spoj.pl/problems/SETNJA/

我使用递归实现了它，但限制非常高，不适合 unsigned long long。在论坛上，每个人都在说使用动态编程来实现它。任何人都可以解释如何使用 DP 来做到这一点。这是我使用递归所做的努力。它是正确的，但答案不适合 unsigned long long。任何提示将不胜感激

#include<stdio.h>

typedef unsigned long long ULLD;
ULLD ans=0ull;
char str[10001];
int length;
void recurse(int i, ULLD temp)
{
    if(str[i]=='\0')
    {
        ans=ans+temp;
        return;
    }
    if(str[i]=='L') recurse(i+1,2*temp);
    else if(str[i]=='R') recurse(i+1,2*temp+1);
    else if(str[i]=='P') recurse(i+1,temp);
    else if(str[i]=='*')
    {
        recurse(i+1, 2*temp);
        recurse(i+1 , 2*temp +1);
        recurse(i+1, temp);
    }
}

int main()
{   
    scanf("%s",str);
    length=strlen(str);

    recurse(0,1);

    printf("%llu",ans);
    return 0;
}