求助

P1464 Function

heart1221 @ 2023-11-23 17:20:04

求助,我在代码中标记的两个部分有什么区别呢? 因为函数要求a,b,c中任意一个大于20的数都会被算成w(20,20,20),那我记忆只要把任意一个大于20的一行都记忆成f[21][21][21],结果反正都一样,等下一个大于20的数来就会直接走记忆化的数组,可是为什么会出现Wrong Ans呢,我不太明白,因为我感觉第一种写法也就是在存储记忆化的过程中,下标不太一致,但是结果是一直的,那我就直接让大于20的都用一个结果都用一个状态不也一样吗,不太明白

#include <iostream>
#include <cstring>

using namespace std;
typedef long long LL;

const LL N =  30;

LL a, b, c;
LL f[N][N][N];

LL w(LL a, LL b, LL c)
{
    // 应该直接return1,否则下标有可能是负的,记忆就会出现segment 
    if(a <= 0 || b <= 0 || c <= 0) return 1;
    else if(f[a][b][c] != -1) return f[a][b][c];
    else if(a > 20 || b > 20 || c > 20) f[a][b][c] = w(20, 20, 20);
    else if(a < b && b < c) 
        f[a][b][c] = w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
    else
        f[a][b][c] = w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);

    return f[a][b][c];
}

int main()
{
    memset(f, -1, sizeof f);
    while(1)
    {
        cin >> a >> b >> c;
        if(a == -1 && b == -1 && c == -1) break;
        printf("w(%lld, %lld, %lld) = ", a, b, c);
      // 第一种写法
        if(a>20) a=21;
     if(b>20) b=21;
     if(c>20) c=21;
       printf("%lld\n",w(a,b,c));
      // 第二种写法
      if(a > 20 || b > 20 || c > 20) printf("%lld\n", w(21,21,21));
        else printf("%lld\n", w(a,b,c));
    }

    return 0;
}

by 瑾阳2012 @ 2023-12-03 14:56:01

@heart1221

你试试这一组样例(用第二种):

30 −1 0

答案为1


|