hzwer.com _ Home | http://hzwer.com

Current position : 首页 >> 决策单调性

• 「BZOJ3675」[Apio2014] 序列分割

  

  Description小H最近迷上了一个分割序列的游戏。在这个游戏里，小H需要将一个长度为N的非负整数序列分割成k+l个非空的子序列。为了得到k+l个子序列，小H将重复进行七次以下的步骤：1．小H首先选择一个长度超过1的序列（一开始小H只有一个长度为n的序列一一也就是一开始得到的整个序列）；2．选择一个位置，并通过这个位置将这个序列分割成连续的两个非空的新序列。每次进行上述步骤之后，小H将会得到一定的分数。这个分数为...
  42015年4月19日8,411斜率优化,决策单调性

• 「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,233决策单调性

• NOI2009诗人小G

  

  DescriptionInputOutput对于每组数据，若最小的不协调度不超过1018，则第一行一个数表示不协调度若最小的不协调度超过1018，则输出"Toohardtoarrange"(不包含引号)。每个输出后面加"--------------------"SampleInput4493brysj,hhrhl.yqqlm,gsycl.492brysj,hhrhl.yqqlm,gsycl.110056poet110046poetSampleOutput108--------------------32--------------------Toohardtoarrange--------------------1000000000000000000---...
  02014年11月29日6,069递推与动规,贪心,决策单调性

• 「BZOJ1010」[HNOI2008] 玩具装箱toy

  

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