洛谷Function(P1464)记忆化搜索or记忆宏
程序员文章站
2024-03-23 20:40:52
...
题目
最简单记忆化搜索
记忆化搜索:算法上依然是搜索的流程,但是搜索到的一些解用动态规划的那种思想和模式作一些保存。
一般说来,动态规划总要遍历所有的状态,而搜索可以排除一些无效状态。搜索还可以剪枝,可能剪去大量不必要的状态,因此在空间开销上往往比动态规划要低很多。
记忆化算法在求解的时候还是按着自顶向下的顺序,但是每求解一个状态,就将它的解保存下来,
以后再次遇到这个状态的时候,就不必重新求解了。
别人代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll rpt[25][25][25];
ll w(ll a,ll b,ll c)
{
if(a<=0||b<=0||c<=0) return 1;
else if(rpt[a][b][c]!=0) return rpt[a][b][c];
else if(a>20||b>20||c>20) rpt[a][b][c]=w(20,20,20);
else if(a<b&&b<c) rpt[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
else rpt[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);
return rpt[a][b][c];
}
int main()
{
ll a,b,c;
while(scanf("%lld%lld%lld",&a,&b,&c)==3){
memset(rpt,0,sizeof(rpt));
if(a==-1&&b==-1&&c==-1) break;
printf("w(%lld, %lld, %lld) = ",a,b,c);
if(a>20) a=21;
if(b>20) b=21;
if(c>20) c=21;
printf("%lld\n",w(a,b,c));
}
return 0;
}
定义记忆宏
看题解看到的,感觉很实用,代码清晰简单,附上AC代码
我的代码
#include <stdio.h>
#include <string.h>
#include <string>
#include <utility>
#include <iostream>
#include <cstdlib>
const int MAXN = 100010;
using namespace std;
//记忆宏,w被求过,就返回w,否则将求得的值先赋给w然后返回
#define W_(x,y,z) (w_[x][y][z] ? w_[x][y][z] : w_[x][y][z] = w(x, y, z))
int w_[25][25][25];
int w(int a,int b,int c){
int ans;
if(a<=0||b<=0||c<=0){
ans=1;
return ans;
}
else if(a>20||b>20||c>20){
return 1048576;//w(20,20,20)
}
if(a < b && b < c)
return W_(a,b,c-1)+W_(a,b-1,c-1) - W_(a,b-1,c);
return 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;
while(cin>>a>>b>>c){
if(a==-1&&b==-1&&c==-1)break;
cout<<"w("<<a<<", "<<b<<", "<<c<<") = "<<w(a,b,c)<<endl;
}
return 0;
}
下一篇: 创建对象使用键值对形式的加深理解
推荐阅读
-
洛谷Function(P1464)记忆化搜索or记忆宏
-
洛谷P4133 [BJOI2012]最多的方案(记忆化搜索)
-
信息学奥赛一本通 1316:【例4.6】数的计数(Noip2001) 洛谷 P1028 记忆化递归(耙耙)
-
巧用记忆化搜索代替暴力递归(洛谷P1464题题解,Java语言描述)
-
HDU - 1331 Function Run Fun 记忆化搜索
-
Function Run Fun 动态规划/记忆化搜索
-
HDU 1331 Function Run Fun(记忆化搜索)
-
HDU1331 Function Run Fun 记忆化搜索
-
[BFS] [记忆化] [洛谷] P1141 01迷宫
-
洛谷P4133 [BJOI2012]最多的方案(记忆化搜索)