Function Run Fun
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 12362 Accepted: 6466
Description
We all love recursion! Don't we?
Consider a three-parameter recursive function w(a, b, c):
if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns: 1 if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
w(20, 20, 20)
if a < b and b < c, then w(a, b, c) returns:
w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
otherwise it returns:
w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
This is an easy function to implement. The problem is, if implemented directly, for moderate values of a, b and c (for example, a = 15, b = 15, c = 15), the program takes hours to run because of the massive recursion.
Input
The input for your program will be a series of integer triples, one per line, until the end-of-file flag of -1 -1 -1. Using the above technique, you are to calculate w(a, b, c) efficiently and print the result.
Output
Print the value for w(a,b,c) for each triple.
Sample Input
1 1 1
2 2 2
10 4 6
50 50 50
-1 7 18
-1 -1 -1
Sample Output
w(1, 1, 1) = 2
w(2, 2, 2) = 4
w(10, 4, 6) = 523
w(50, 50, 50) = 1048576
w(-1, 7, 18) = 1
Source
POJ1579
题目一开始就说了We all love recursion! Don't we?(我们都喜欢递归!不是吗?)但从这道题目的复杂度来看,用递归来解决的话必然TLE,因此还是类似斐波那契数列的思路,用空间换时间。
代码如下:
#include<stdio.h>
int w[21][21][21] = {1};
int getw(int a, int b, int c){
if(a <= 0 || b <= 0 || c <= 0)
return 1;
else if(a > 20 || b > 20 || c > 20)
return w[20][20][20];
else
return w[a][b][c];
return 1;
}
int main(){
int a, b, c;
for(a = 1; a <= 20; ++a){
for(b = 1; b <= 20; ++b){
for(c = 1; c <= 20; ++c){
if(a < b && b < c){
w[a][b][c] = getw(a, b, c-1) + getw(a, b-1, c-1) - getw(a, b-1, c);
}else{
w[a][b][c] = getw(a-1, b, c) + getw(a-1, b-1, c) + getw(a-1, b, c-1) - getw(a-1, b-1, c-1);
}
}
}
}
while(scanf("%d%d%d", &a, &b, &c) && (a + 1) || (b + 1) || (c + 1))
printf("w(%d, %d, %d) = %d\n", a, b, c, getw(a, b, c));
return 0;
}
话说这是我在北京大学ACM上做的第二道题,第一道题是:动态规划入门(一)The Triangle,两道题都是一次通过,让我对北京大学在线评测系统的印象分顿时提高不少 [偷笑] 。。
=======================签 名 档=======================
原文地址(我的博客):http://www.clanfei.com/2012/04/436.html
欢迎访问交流,至于我为什么要多弄一个博客,因为我热爱前端,热爱网页,我更希望有一个更加自由、真正属于我自己的小站,或许并不是那么有名气,但至少能够让我为了它而加倍努力。。
=======================签 名 档=======================
分享到:
相关推荐
poj两道题的c++实现。已经测试过可以通过oj
北大ACM在线评测系统POJ的题目非常之多,如果只盲目做题,恐难以各种类型题目考虑周全。此列表把各种题型做分类,按照此表可做针对性练习。献给所有愿意ACM刚入门的童鞋。。
北大ACM在线评测系统POJ的题目解题报告。涵盖各种类型的acm题目。值得参考借鉴。打包下载。
Pku acm 第1579题 Function Run Fun 代码,有详细的注释,动态规划
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
POJ上面题目的解题报告。涵盖挺多的。可作参考。代码都正确。ACM新手入门必下~~ 加油...
ACM PKU_poj 1197 仓库问题源代码,愿与大家共享。若谁更好的代码,多谢提供。
ACM_算法模板集史上最完整收藏版223页全免费版.pd
背包九讲2.0_算法_动态规划_ACM_
博弈论的经典入门书,适合于学习ACM的人或想学习写AI的人-Classic introductory book on game theory, ACM for learning to write the person or AI who want to learn 对于搞ACM/ICPC有很大帮助,里面涉及博弈论,...
在进行ACM编程训练时做字符串专题的一些题目(POJ1782,POJ1790,POJ1951,POJ2003,POJ2121)
杭电hdu acm资料所用杭电的acm题
浙江大学ACM题解JU_ACM_All_Anwer,里面一本非常好的chm电子书,浙大的所有ACM题及题解都在了,对学习ACM的朋友非常的好~还等什么呢?
acm,动态规划类问题分析,并附有这些问题的详细代码
noi试题和解析,对于参加acm非常有帮助
ACM_基础篇
ACM_exercisecodeforOVaOJconnectingto算法竞赛入门训练指南.zip
本文件是ACM里的一些题目的源码、原题和习题的分析及详细解答。欢迎各位下载
Pascal acm_timus_ural_1148.pas