最佳团体[JSOI2016]

https://www.luogu.com.cn/problem/P4322 题解网上怎么这么多O(n^3\log n)假做法啊。。。一条链就卡掉了 假设0号节点是根 建出表示依赖关系的图 发现正好有n条边且每个点的父亲都比它编号小所以正好是一棵树 那么原问题就是要在树上取一个包含根的性价比最高的连通块 看到”性价比”考虑使用01分数规划 假设x_i\in \{0,1\}表示第i个人选不选 ...

Earthquake[USACO01OPEN]

题目描述一场地震把约翰家的牧场摧毁了, 坚强的约翰决心重建家园。 约翰已经重建了$n$个牧场,现在他希望能修建一些道路把它们连接起来。研究地形之后,约翰发现可供修建的道路有$m$条。碰巧的是,奶牛们最近也成立一个工程队,专门从事修复道路。而然,奶牛们很有经济头脑,如果无利可图,它们是不会干的。 奶牛们关注的是挣钱速度,即总利润和总施工时间的比值。约翰和奶牛达成了协议,奶牛负责修建道路,将所有...

送礼物「JSOI 2015」

【题目描述】礼品店一共有N件礼物排成一列,每件礼物都有它的美观度。排在第$i(1\leq i\leq N)$个位置的礼物美观度为正整数$A_I$。JYY决定选出其中连续的一段,即编号为礼物$i,i+1,…,j-1,j$的礼物。选出这些礼物的美观程度定义为:$(M(i,j)-m(i,j))/(j-i+K)$,其中$M(i,j)$表示$max{A_i,A_{i+1}\dots A_j}$,$m(...