POJ1579
题目需要你需要实现以下函数的功能:

int w(int a,int b,int c){//原始的函数
    if(a<=0||b<=0||c20||b>20||c>20)return 1048576;
    else if(a<b&&b<c)return (w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c));
    else return (w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1));
}


按照上述的方式直接调用 会超时。。。
自己用电脑 骚骚了一下 20 20 20 等了好久的说。。。
试着用数组存储下每一次获得的结果(下面的代码还可以优化 懒了)
会减少大量的递归查询时间
方法1: 440K 0MS 787B

#include<stdio.h>
#include<string.h>
int vis[22][22][22];
int value[22][22][22];
int w(int a,int b,int c){
    if(a<=0||b<=0||c<=0)return 1;
    else if(a>20||b>20||c>20)return 1048576;
    else if(a<b&&b<c){
        if(!vis[a][b][c]){
            value[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-
                            w(a,b-1,c);
            vis[a][b][c]=1;
        }
        return value[a][b][c];
    }
    else {
        if(!vis[a][b][c]){
            value[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);
            vis[a][b][c]=1;
        }
        return value[a][b][c];
    }
}
int main(){
    int i,j,a,b,c;
    while(scanf("%d%d%d",&a,&b,&c)!=EOF){
        if(a==-1&&b==-1&&c==-1)break;
        printf("w(%d, %d, %d) = %d\n",a,b,c,w(a,b,c));
    }
    return 0;
}

方法2:400K 0MS 904B

#include<stdio.h>
int value[22][22][22];
int main(){
    int i,j,k,a,b,c;
    for(i=0;i<=21;i++){
        for(j=0;j<21;j++){
            value[i][j][0]=value[i][0][j]=value[0][i][j]=1;
        }
    }
    for(i=1;i<21;i++){
        for(j=1;j<21;j++){
            for(k=1;k<21;k++){
                if(i<j&&j<k)
                    value[i][j][k]=value[i][j][k-1]+
                    value[i][j-1][k-1]-value[i][j-1][k];
                else
                    value[i][j][k]=value[i-1][j][k]+
                    value[i-1][j-1][k]+value[i-1][j][k-1]-
                    value[i-1][j-1][k-1];
            }
        }
    }
    while(scanf("%d%d%d",&a,&b,&c)!=EOF){
        if(a==-1&&b==-1&&c==-1)break;
        else if(a<=0||b<=0||c<=0)
            printf("w(%d, %d, %d) = 1\n",a,b,c);
        else if(a>20||b>20||c>20)
            printf("w(%d, %d, %d) = 1048576\n",a,b,c);
        else
            printf("w(%d, %d, %d) = %d\n",a,b,c,value[a][b][c]);
    }
    return 0;
}
原创文章采用 CC BY-NC-SA 4.0协议 进行许可,转载请著名转自: poj 1579 function run fun DP记忆化

0 评论