Function Run Fun[1579@pku]

//@pku 1579 DY问题
//采用的是备忘录方式
//主要的问题是在dp()前,先检查一下下标
#include<iostream>
#include<fstream>
using namespace std;

#define N 24
#define fin cin
int v[N][N][N];
int dp(int a,int b,int c);

int main()
{
    //ifstream fin("input.txt");
    int a,b,c;
    memset(v,-1,sizeof(v));//只需要初始化一次
    while(fin>>a>>b>>c){
        if(a==-1 && b==-1 && c==-1)
            break;
        int sum;
        if(a<=0 || b<=0 || c<=0)
            sum=1;
        else if(a> 20 || b>20 || c>20)
            sum=dp(20,20,20);
        else 
            sum=dp(a,b,c);
        cout<<"w("<<a<<", "<<b<<", "<<c<<") "<<"= "<<sum<<endl;
    }//end while
    return 0;
}

int dp(int a,int b,int c)
{
    if(a<=0 || b<=0 || c<=0)
        return 1;
    if(v[a][b][c]!=-1)
        return v[a][b][c];
    else
    {
        if(a<b && b<c)
            return v[a][b][c]=dp(a,b,c-1)+dp(a,b-1,c-1)-dp(a,b-1,c);
        else
            return v[a][b][c]=dp(a-1, b, c) + dp(a-1, b-1, c) + dp(a-1, b, c-1) - dp(a-1, b-1, c-1);
    }
}

posted on 2012-02-27 10:10 DjvuLee 阅读(169) 评论(0)  编辑 收藏 引用 所属分类: 动态规划


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2012年2月>
2930311234
567891011
12131415161718
19202122232425
26272829123
45678910

统计

常用链接

留言簿

随笔分类(13)

随笔档案(19)

文章分类(2)

文章档案(1)

搜索

最新评论

评论排行榜