热身赛总结 题解
1. 旅行计划赛时思路
因为目标是：求出一直向东以城市 \(i\) 为终点最多能够游览多少个城市，我进行逆向思维，转换题意，将目标改成：以城市 \(i\) 为起点一直向西最多能够游览多少个城市，再看题目的数据范围：$n \le 10^5 $，因此便直接用 dfs 进行搜索，最后 TLE 了4个点 QwQ 。
改进思路
因为题目中说图中没有环，因此我们可以通过 DP 解决此题，所以我们就可以通过记忆化递归防止进行无效的 dfs 。
AC代码
点开有惊喜#include#define ll long longusing namespace std;ll n,m,x,y,dp;vectort;ll dfs(ll x,ll val){ if(!t.size()) return val; ll mx=0; for(auto y:t){ if(!dp) dp=dfs(y,val); mx=max(mx,dp); } return mx+1;}int main(){ cin>>n>>m; for(int i=1;i>x>>y; t.push_back(x); } for(int i=1;i>x; zh[++cnt]=x; cxa(1,1,n,x,1); } else if(ch=='Q'){ cin>>x; if(!check(1,1,n,x)){ coutm; for(int i=1;i>a; l=max(l,a); r+=a; } while(l 鼓励转贴优秀软件安全工具和文档！ 收藏一下 不知道什么时候能用到 前排留名，哈哈哈
页:
[1]