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(...