每日归档： 2022年1月3日

T1：期望dp，设F节点有儿子C1…CN，因为是排列，Ck不是再C1前就是再C1后，即Ck对C1的贡献为S[Ck]/2,其他同理，再加上直接从父节点转移的1即可

T2：正解，逆向dp

T3：AC自动机上DP+矩乘

T4：floyd+贪心/费用流，先处理最短路，然后枚举两个不同的点A（X₁，Y₁），B（X₂，Y₂）得到n个点到A的时间a[]以及到B的时间b[]，这个问题就变成了找出集合S1，S2，S1∩S2是空集,S1∪S2={1,2…n}，|S1|=|S2|=n/2，使得∑a[i]+∑b[j](i∈S1,j∈S2)最小（语言表达力有限，请谅解）

这个问题显然可以贪心，设c[i]为把a[i]变为b[i]的代价，我们先全选a[]，记和为sum，然后将最大的n/2个c[i]减去即可，时间复杂度O(r²c²nlogn)费用流的方法我还不会

总结：我还是得多角度分析问题，T1一直在想枚举排列，结果就没有思路了

欢迎使用 WordPress！这是您的第一篇文章。编辑或删除它，开启您的博客之旅。