Function Run Fun [ZOJ – 1168]解读

Function Run Fun [ZOJ – 1168]解读

题目:
https://zoj.pintia.cn/problem-sets/91827364500/problems/91827364667

题目给出接受三个参数的函数递归式

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
1

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
w(20, 20, 20)

if a < b and b < c, then w(a, b, c) returns:
w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns:
w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

如果直接写成递归式肯定会超时,就像 ackerman (n,m)函数,收敛非常慢。就是因为计算的时候做了非常多的重复计算,所以可以把已经算过的数值保存下来,开一个数组,初始值为w()函数取不到的值,若算出来就更新其值,用到的时候就直接读取,会减少很多计算的时间从而顺利解决。有初步的动规思想

#include <cstdio>
#include <cstring>

int w[21][21][21];

int fw(int a,int b,int c)
{
    if( a<=0 || b<=0 || c<=0)
        return 1;
    if ( a>20 || b>20 || c>20 )
        return fw(20,20,20);
    
    if(w[a][b][c]>0)
        return w[a][b][c];
    else
    {
        if ( a<b && b<c )
        {
            w[a][b][c]=fw(a,b,c-1)+fw(a,b-1,c-1)-fw(a,b-1,c);
            return w[a][b][c];
        }
        else
        {
            w[a][b][c] = fw(a-1,b,c)+fw(a-1,b-1,c)+fw(a-1,b,c-1)-fw(a-1,b-1,c-1);
            return w[a][b][c];
        }
    }
}

void init()
{
    memset(w,0,sizeof(int)*21*21*21);    
    int a,b,c,i;
    for(i=0;i<=20;i++)
    {
        w[0][0][i]=1;
        w[0][i][0]=1;
        w[i][0][0]=1;

        w[i][i][0]=1;
        w[i][0][i]=1;
        w[0][i][i]=1;
    }


}

int main(void)
{
    int a,b,c;
    init();
    while(1)
    {
        scanf("%d%d%d",&a,&b,&c);
        if(a==-1 && b==-1 && c==-1)
            break;
        printf("w(%d, %d, %d) = ",a,b,c);
        printf("%d\n",fw(a,b,c) );
    }
    return 0;

}

发表评论

电子邮件地址不会被公开。 必填项已用*标注