• 「BZOJ3675」[Apio2014] 序列分割

    「BZOJ3675」[Apio2014] 序列分割

    Description小H最近迷上了一个分割序列的游戏。在这个游戏里,小H需要将一个长度为N的非负整数序列分割成k+l个非空的子序列。为了得到k+l个子序列,小H将重复进行七次以下的步骤:1.小H首先选择一个长度超过1的序列(一开始小H只有一个长度为n的序列一一也就是一开始得到的整个序列);2.选择一个位置,并通过这个位置将这个序列分割成连续的两个非空的新序列。每次进行上述步骤之后,小H将会得到一定的分数。这个分数为...

    42015年4月19日8,122斜率优化,决策单调性
  • 「BZOJ2216」[POI2011] Lightning Conductor

    「BZOJ2216」[POI2011] Lightning Conductor

    Description已知一个长度为n的序列a1,a2,...,an。对于每个1<=i<=n,找到最小的非负整数p满足对于任意的j,aj<=ai+p-sqrt(abs(i-j))Input第一行n,(1<=n<=500000)下面每行一个整数,其中第i行是ai。(0<=ai<=1000000000)Outputn行,第i行表示对于i,得到的pSampleInput6532424SampleOutput235354题解倒腾一下式子得出f[i]=max{a[j]+sqrt(abs(i-j))}-a[i]为了把绝对值去掉就正反各做一次取最大值这个式子显...

    52014年11月29日6,011决策单调性
  • NOI2009诗人小G

    NOI2009诗人小G

    DescriptionInputOutput对于每组数据,若最小的不协调度不超过1018,则第一行一个数表示不协调度若最小的不协调度超过1018,则输出"Toohardtoarrange"(不包含引号)。每个输出后面加"--------------------"SampleInput4493brysj,hhrhl.yqqlm,gsycl.492brysj,hhrhl.yqqlm,gsycl.110056poet110046poetSampleOutput108--------------------32--------------------Toohardtoarrange--------------------1000000000000000000---...

    02014年11月29日5,743递推与动规,贪心,决策单调性
  • 「BZOJ1010」[HNOI2008] 玩具装箱toy

    「BZOJ1010」[HNOI2008] 玩具装箱toy

    DescriptionP教授要去看奥运,但是他舍不下他的玩具,于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩,其可以将任意物品变成一堆,再放到一种特殊的一维容器中。P教授有编号为1...N的N件玩具,第i件玩具经过压缩后变成一维长度为Ci.为了方便整理,P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具,那么两件玩具之间要加入一个单位长度的填充物,形式地说如果将第i件玩具到第...

    72014年11月28日24,546斜率优化,决策单调性