是记忆化搜索！
2025-12-16 22:24:46
发布于：上海
嘻嘻嘻嘻嘻嘻嘻我喜欢记忆化搜索，我要拿SHNOIP1=！！！
开始时间：2025/12/16 20:44
那么先来一道友善小题目入入手吧！
链接描述
给出n个物种和m条流动关系，求其中食物链条数。
M条流动关系：a1,b1：能量从a1流向物种b1。
注意单独的一种孤立生物不算一条食物链。
其实这题大概率用拓扑排序也能做吧。
就是找入读为零的点到出度为零的点一共有多少条路径嘛。
那先搓一个普通DFS好了。
哇塞运气好好！过了七个点！
普通DFS展示：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int>v[N];
int rd[N],cd[N];//统计入度和出度
typedef long long ll;
ll ans=0;
void dfs(int x){
for(int i=0;i<v[x].size();i++){
int to=v[x][i];
if(cd[to]==0){
ans++;
continue;
}
dfs(to);
}
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
v[x].push_back(y);
rd[y]++;
cd[x]++;
}
for(int i=1;i<=n;i++){
if(rd[i]==0&&cd[i]!=0){
dfs(i);
}
}
cout<<ans;
return 0;
}
记忆化搜索的思路大概就是：我在进行下一轮dfs搜索之前，我去用一个变量（比如说sum)去记录一下ans的值，然后等这一轮dfs结束回来后，ans的值可定不一样嘛（因为有新路径，所以会增加）然后此时，我的mem[to]就可以是ans-sum。
但是编写代码的时候又是感觉怪怪的。
所以我再次对我的思路进行了纠正，我将dfs的返回值改为了long long 而不是 void。
将ans已到了主函数内。然后每次让mem[x]加上它for循环这一轮里创造出来的方案数（有点抽象，可以按看代码）。
然后就过了。
不过中间还有一个小插曲：我按照自己的习惯将mem赋值为了-1，但是却忽略了我这次的代码是直接在mem上进行加减的，而不是像往常一样的：函数赋值。所以后来又改回了9。
看看代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int>v[N];
int rd[N],cd[N];//统计入度和出度
typedef long long ll;
ll mem[N];
ll dfs(int x){
if(mem[x]!=0)return mem[x];
for(int i=0;i<v[x].size();i++){
int to=v[x][i];
if(cd[to]==0){
mem[x]++;
continue;
}
mem[x]+=dfs(to);
}
return mem[x];
}
int main(){
memset(mem,0,sizeof mem);
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
v[x].push_back(y);
rd[y]++;
cd[x]++;
}
ll ans=0;
for(int i=1;i<=n;i++){
if(rd[i]==0&&cd[i]!=0){
ans+=dfs(i);
}
}
cout<<ans;
return 0;
}
呃呃呃然后斗胆开一题从来没接触过的紫……试试看吧
链接描述
控制游戏角色来获得尽可能多的分数。
游戏界面离散为一个长度为1-n，高度为1-m（初始点为(0,1)）的矩阵图。
每个格子上都有收益(-1 - 1000)，-1表示该点不能通过。
游戏角色从起点一路奔跑向终点，中途可以通过跳跃来获得更高的分数，在空中还能进行连跳。
游戏开始前，你可以设定跳跃的高度，以及能连跳的次数。
初始跳跃高度为1，连跳数为1（最多为5）
升级跳跃高度和连跳都需要一定的花费。
跳跃高度设定后，游戏角色每次条约高度都固定
连跳则可以在下落过程中使用。
所有操作都将在整点上完成。
需要保证设定完的跳跃高度及连跳次数，无法跳出游戏高度上线
啊啊啊有点复杂啊，看看能不能做个普D出来，A它20%。
写着写着突然发现华点：m<=20。所以后面的记忆化搜索应该就是从这个点突破吧。
呜呜呜哇哇哇注意这是m * n不是n*m
但是它所谓的“终点”是什么？
电量耗尽了，去做whk作业了。
结束时间：2025/12/16 22:23
这里空空如也
有帮助，赞一个