poj 1579 Function Run Fun

poj 1579 Function Run Fun

/*
用到了dp中记忆化搜索的思想
填表记录来减少递归时的重复调用 
*/
#define LOCAL
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<string>
#include<algorithm>
#include<ctime>
#include<stack>
#include<queue>
#include<vector>
#define N 25
using namespace std;
int map[N][N][N];
int w(int a,int b,int c)
{
           if(a<=0||b<=0||c<=0) return map[0][0][0]=1;
           if(a>20||b>20||c>20) return map[20][20][20]=1048576;
           if(map[a][b][c]) return map[a][b][c];
           if(a<b&&b<c){return map[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);}
           return map[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);  
}
int main()
{
#ifdef LOCAL
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
#endif
 
        int x,y,z;
        memset(map,0,sizeof(map));
        while(cin>>x>>y>>z&&(!(x==-1&&y==-1&&z==-1)))
            printf("w(%d, %d, %d) = %d\n",x,y,z,w(x,y,z));       
        return 0;
}

发表回复

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