对于状态可以一次性遍历而确定的类型--推荐使用记忆化搜索，一般额外用一个数组(f[], f[][])来记录当前位置的状态。最近做了好几道记忆化搜索题\dp题，先挂上来一道觉得较典型的记录下学习的轨迹。原题：食物链~
大量数据输入--快读优化；
复习了一下链式向前星存图：
1）head[point]可看作以point为起点的所有边的集合(本质上就是point的某个出度)，数组的大小为点的总数。head[point]为集合中边的编号的最大值。这个多用几次就会逐渐理解。
2）edge[cur]数组存的是边，所以开的数组大小是边数。next用来将起点相同的边连成一个集合，point就像是一个泡沫板，起点相同的edge通过next像插气球一样插到point这泡沫板上,所以在访问point的所有边时，一直遍历next，直到泡沫板上的气球都被访问完。
记忆化搜索：f[](一维，二维具体视情况而定)记录状态，再次遍历的时候就可以直接返回确定过的状态。
/**链式向前星 + 记忆化dfs搜索 大数据记得要开long long, MLE就是这么来滴 ~ 链式向前星存的是边, cur为当前边的标号,note that 数组的大小要是边的数量!! **/ #include <cstdio> #include <cstring> using namespace std; #define uint unsigned int #define ll long long const int maxn = 100005;//总的最大点数,边数记得乘2,或者再开一个最大边数! /** next: 于当前边起点一样的另一条边的编号 每个edge[i] 存的是一条边 head[i]: 以i编号为起点的边的最大编号 因为边的编号 cur 从0开始,所以 head[] 初始为-1， 当然也可以使 cur 从1开始,这样就不必消耗时间将 head 初始化 **/ struct Edge{ int to, next, w; }edge[maxn<<1]; ll f[maxn], sum; //状态方程 int head[maxn], n,m, cur=1; uint in[maxn]; inline int read(){ int ans = 0; char ch = getchar(); while(ch<‘0‘ || ch>‘9‘) ch = getchar(); while(ch>=‘0‘ && ch<=‘9‘){ ans = (ans<<3) + (ans<<1) + ch-‘0‘; ch = getchar(); }return ans; } /** 1.当前边进入from为起点的集合 2.本边的另一个端点 3.当前边的编号(from集中目前最大的编号)记录到 head[from]. **/ inline void addEdge(int from,int to){ if(from == to) return; edge[cur].next = head[from]; edge[cur].to = to; head[from] = cur++; } ll dfs(int q){ if(f[q]) return f[q]; if(!in[q] && !head[q]) return 0;//单个物种 if(in[q] && !head[q]){ //结尾点 f[q] = 1; return f[q]; } ll tmp_sum = 0; for(int i=head[q];i;i=edge[i].next){ tmp_sum += dfs(edge[i].to); } f[q] = tmp_sum; return f[q]; } int main() { n = read(), m = read(); int u,v; for(int i=0;i<m;++i){ u = read(), v = read(); if(u ^ v) in[v] = true; addEdge(u,v); } for(int i=1;i<=n;++i){ if(!in[i] && head[i])//食物链的首 sum += dfs(i); } printf("%lld\n", sum); return 0; }
原文：https://www.cnblogs.com/GorgeousBankarian/p/11050481.html