夢に僕らで帆を張って
来るべき日のために夜を超え

标签 记忆化搜索 下的文章

November 3, 2019

洛谷P3183/HAOI2016 食物链

题意给出$n$个物种和$m$条关系,求食物链条数数据范围:$1 \le n \le 100000,0 \le m \le 200000$题解记忆化搜索食物链从入度为$0$的点开始,到出度为$0$的点结束注意单独的一种孤立生物不算一条食物链代码:#include<iostream> #include<cstdio> using namespace std; const ...
October 21, 2019

洛谷P3953 逛公园

题意求长度$\le$最短路$+k$的路径数数据范围:$n \le 100000,m \le 200000$题解首先需要跑一边最短路找到这个最短路;虽然保证存在$1 \rightarrow n$的路径,但并不是所有的点都能到$n$,所以应跑反向图用$f[u][i]$表示从$u$到$n$的路径中$\le dis[u][n]+i$的路径数,则答案为$f[1][k]$对于转移,考虑一条边$u \ri...