首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。