锐客网

  1. 首页 > it技术 > >

DP|[CF868E]Policeman and a Tree

dp博弈

题目大意
给你一颗有n个点的树，每条边有边权，有一个警察一开始在点S，他的速度是1，即通过一条长度为x的边要花x单位时间。
有m个罪犯，一开始第i个在点x[i]，他们的速度无限快。
如果罪犯和警察到达同一个点，那么罪犯会被抓住。
现在罪犯们想最大化最后一个被抓的时间，警察想最小化抓的时间。
n<=50
解题思路
【DP|[CF868E]Policeman and a Tree】不看wxh的博客都不会qwq
我们从一开始的局面考虑。
警察在点S，现在罪犯分布在各个子树里，假设子树x原本有siz[x]个罪犯，警察会选一个子树走进去，使得时间最小，而每颗子树的罪犯则会走动，使得警察难以抓住。假如他选子树x走进去，那么就变成另外一个问题了，警察在点x，从S走来，x子树里有siz[x]个罪犯，算上这些还有m个罪犯没有被抓。
现在，x子树内的罪犯又会重新分配位置，然后继续决策。直到警察走到一个叶子结点，抓了一些罪犯，那么总罪犯减少，又变成子问题了。
所以设f(x,y,cnt,tot)。四元组状态表示警察在x点，他从y走来（最优决策的话，走到叶子前不可能折返），当前x子树有cnt个罪犯（分布还未确定），总共还有tot个罪犯没被抓。f()表示在此状态下警察抓完所有人的最短时间。
考虑转移。
边界：如果到叶子结点，那么抓到cnt个人，tot-=cnt，返回去继续抓。抓完了返回0。如果cnt=0，走进这棵子树没有意义，返回inf。
现在假设x点有k个儿子，设在第i个儿子分布了a[i]个罪犯，其中 ∑i=1..ka[i]=cnt∑ i = 1.. k a [ i ] = c n t ；假设a[]已经确定，警察为了时间尽量短，选择f(son[i],x,a[i],tot)最小的那个i；反过来，罪犯为了使得抓捕时间长，一定会使得a[]里面f值最小的儿子尽量大。这个用dp实现就可以求出最终的抓捕时间，就是把cnt个元素分k份的过程。
时间复杂度 O(n5)O ( n 5 )
代码

#include #include #include #include #include #include //开 O2！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！ using namespace std; #define fo(i,j,k) for(i=j; i<=k; i++) #define fd(i,j,k) for(i=j; i>=k; i--) #define cmax(a,b) (a=(a>b)?a:b) #define cmin(a,b) (a=(a

    推荐阅读


    上一篇：回文树/回文自动机|回文树/回文自动机 Palindromic Tree 学习小记

    下一篇：时间戳，随机串工具