CF1606E
思维难度:\(\color{#52C41A} 绿\) *1700
如何设计状态?
首先第一维一定是剩余 \(i\) 个人,这个是毫无疑问的。
然后看我们实际上关心的是什么。因为要算没有人胜利的方案数,而如果有人胜利,那么这个人一定是初始状态下所有人中血量最大的,且在后面的过程中也能一直保持最大。所以不妨把当前局面的最大血量丢到状态里,令 \(f_{i,j}\) 为剩余 \(i\) 个人,其中最大血量为 \(j\),最终没有胜者的方案数。
发现这是正确的,转移只需要考虑血量最大的人是否存活到下一轮即可。
submission
天依宝宝可爱!