Original link: https://www.shuizilong.com/house/archives/atcoder-beginner-contest-281/
#AtCoder Beginner Contest 281
– [https://atcoder.jp/contests/abc281/tasks](https://atcoder.jp/contests/abc281/tasks)
## C
Classic two stacks.
##D
Backpack.
## E.
Classic Tire tree DP.
## G.
Combine dp. The game reads:
dp[i][j][k]: the first i layer uses j vertices, and the i layer uses k vertices.
Transfer O(n) A total of O(n4) It turns out that there is no way to simply use prefixes and reduce complexity.
The correct way is to simplify the state! Regardless of how many layers are divided, directly use the number of vertices that have been investigated to divide the stage:
dp[i][j]: A total of i vertices are used, and j vertices are used in the outermost layer.
## Ex.
Construct generating function and paste polynomial template.
– [https://zhuanlan.zhihu.com/p/590914324](https://zhuanlan.zhihu.com/p/590914324)
This article is transferred from: https://www.shuizilong.com/house/archives/atcoder-beginner-contest-281/
This site is only for collection, and the copyright belongs to the original author.