记忆化搜索 hdu 1331
搜索 HDU 记忆
2023-09-27 14:23:30 时间
Function Run Fun
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2586 Accepted Submission(s): 1255
Problem 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.
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
非常明显此题通过模拟来做,递归次数太多一定非常浪费时间。不能过去。
能够通过空间换时间的方法。将计算出的值
存储在数组中。然后将全部可能计算出来的值计算一下子就能够了。直接输出就可以。
//考查知识点:记忆化搜索 就是用数组存储。降低递归函数调用的次数和时间 //考试当天做出来了。今天又做一遍,居然有点生疏了,(⊙﹏⊙)b #include<stdio.h> int s[22][22][22]; void f() { int i,j,k; for(i=1;i<22;++i) { for(j=1;j<22;++j) { for(k=1;k<22;++k) { if(i<j&&j<k) { if(k-1==0) s[i][j][k-1]=s[i][j-1][k-1]=1; if(j-1==0) s[i][j-1][k-1]=s[i][j-1][k]=1; s[i][j][k]=s[i][j][k-1]+s[i][j-1][k-1]-s[i][j-1][k]; continue; } if(i==1) s[i-1][j][k]=s[i-1][j-1][k]=s[i-1][j][k-1]=s[i-1][j-1][k-1]=1; if(j==1) s[i-1][j-1][k]=s[i-1][j-1][k-1]=1; if(k==1) s[i-1][j][k-1]=s[i-1][j-1][k-1]=1; s[i][j][k]=s[i-1][j][k]+s[i-1][j-1][k]+s[i-1][j][k-1]-s[i-1][j-1][k-1]; } } } } int main() { int a,b,c; f(); while(~scanf("%d%d%d",&a,&b,&c),!(a==-1&&b==-1&&c==-1)) { if(a<=0||b<=0||c<=0) { printf("w(%d, %d, %d) = 1\n",a,b,c); continue; } if(a>20||b>20||c>20) { printf("w(%d, %d, %d) = %d\n",a,b,c,s[20][20][20]); continue; } printf("w(%d, %d, %d) = %d\n",a,b,c,s[a][b][c]); } return 0; }
相关文章
- 【视频开发】ONVIF客户端搜索设备获取rtsp地址开发笔记(精华篇)
- Confluence 6 移动浏览搜索内容和人
- 特殊字符搜索网站 http://symbolhound.com/
- C语言实现二叉搜索树
- hdu 4634 Swipe Bo 搜索
- 百度下线搜索快照功能,内部人士:因技术升级导致功能淘汰;法国App开发者集体起诉苹果;Linux 5.19 发布|极客头条
- hdu 1728 搜索求最少的转向次数
- 9-7-平衡二叉排序(搜索)树-查找-第9章-《数据结构》课本源码-严蔚敏吴伟民版
- 【算法】深度优先搜索 (DFS)
- 传智播客 朴素贝叶斯 算法评估 交叉验证与网格搜索 学习
- HDU 4597 Play Game (DP,记忆化搜索)
- HDU 4634 Swipe Bo (2013多校4 1003 搜索)
- 中国人工智能学会通讯——搜狗搜索:从搜索到问答 1.4 搜索的未来
- LeetCode·每日一题·864.获取所有钥匙的最短路径·广度优先搜索
- MR小区搜索(六)cell reselection
- HDU 1885 Key Task 国家压缩+搜索
- 搜索EE场景排序链路升级
- 【Windows 逆向】使用 CE 工具挖掘关键数据内存真实地址 ( 数据查找技巧 | 地址访问调试 | 指令选择技巧 | MOV 汇编指令含义 | 基址值搜索 ) ★
- 在ubuntu下如何搜索文件?