首页 > 代码库 > poj 1579 Function Run Fun

poj 1579 Function Run Fun

题目链接:http://poj.org/problem?id=1579

 

思路:

        题目给出递归公式,使用动态规划的记忆搜索即可解决。

代码:

 

#include <stdio.h>#include <string.h>const int MAX_N = 20 + 5;int dp[MAX_N][MAX_N][MAX_N];int w( int a, int b, int c ){    if ( dp[a][b][c] != -1 )        return dp[a][b][c];    if ( a <= 0 || b <= 0 || c <= 0 )        return dp[a][b][c] = 1;    else    if ( a < b && b < c )        return dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);    else        return dp[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(){    int a, b, c;    int ans = 0;    while ( scanf( "%d %d %d", &a, &b, &c ) != EOF )    {        if ( a == -1 && b == -1 && c == -1 )            break;        memset( dp, -1, sizeof(dp) );        if ( a <= 0 || b <= 0 || c <= 0 )            ans = 1;        else        if ( a > 20 || b >20 || c > 20 )            ans = w(20, 20, 20);        else            ans = w(a, b, c);        printf( "w(%d, %d, %d) = %d\n", a, b, c, ans );    }    return 0;}

 

poj 1579 Function Run Fun