New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

2022-9-29总结 | Ptilopsis_w's little blog #33

Open

Ptilopsisw opened this issue Sep 30, 2022 · 0 comments

Labels

b1c51f79e0196dea9efd65836bfafaba Gitalk

Owner

Ptilopsisw commented Sep 30, 2022

https://ptilopsisw.github.io/2022/09/30/2022-9-29%E6%80%BB%E7%BB%93/

分身游走看到 k≤30k \le 30k≤30 ，就大概想到是个关于 kkk 的 DP, 然而太菜了当时连暴力 DP 都写不出来。观察性质：在最优方案中，一定不会出现超过一个分身进入以 xxx 为根的子树又回到 xxx 的父亲的情况。在最优方案中，如果有至少两个分身进入了以 xxx 为根的子树，那么这些分身都应该停在以 xxx 为根的子树内。用这两条性质可以将 DP 优化到

Ptilopsisw added Gitalk b1c51f79e0196dea9efd65836bfafaba labels

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment