- UID
- 739901
- 在线时间
- 3 小时
- 最后登录
- 2023-2-25
- 注册时间
- 2014-4-1
- 宅魂
- 609 点
- 贡献
- 68 点
- 宅币
- 4804 枚
- 宅の石（入宅度）
- 50 块
- 元气（技能点）
- 2 点
- 活跃
- 98 ℃
- 听众
- 10
- 收听
- 0
签到天数: 8 天 连续签到: 1 天 [LV.3]偶尔看看II
序章
- 积分
- 6987
|
楼主 |
发表于 2019-11-12 22:39:46
|
显示全部楼层
记忆化搜索
在网上找了一个比较典型的记忆化搜索的题目
对于一个递归函数w(a,b,c)
如果 a<=0 or b<=0 or c<=0 就返回值1
如果 a>20 or b>20 or c>20就返回w(20,20,20)
如果 a<b并且b<c 就返回w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,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)
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long LL;
- const int MAX=30;
- int f[MAX][MAX][MAX]; //用数组记录，全局变量的初始值为0
- int w(int a,int b,int c)
- {
- if(f[a][b][c]!=0) //不等于0即为已经搜索过，可以返回该值
- return f[a][b][c];
- if(a<=0||b<=0||c<=0)
- return 1;
- if(a>20||b>20||c>20)
- return f[a][b][c]=w(20,20,20);
- if(a<b&&b<c)
- return f[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c-1);
- return f[a][b][c]=w(a-1,b,c)+w(a-1,b-1,b)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
- } //返回时用f[a][b][c]=是为了记录该处的值，减少重复搜索的次数
- int main()
- {
- int a,b,c;
- while((scanf("%d%d%d",&a,&b,&c))!=EOF)
- {
- cout<<w(a,b,c)<<endl; //这里是偷懒直接输出要搜索的值了，具体输出看具体题目要求
- }
- return 0;
- }
|
|
发新帖
发表于 2019-11-12 22:33:35
提升卡
置顶卡
变色卡