[洛谷P1080]国王游戏[贪心,高精]

题面

贪心策略: 按照每个大臣左右手的乘积升序排列为最优解.

这可以采用临项交换的方法证明, 常见于涉及以某关键字排序的贪心策略.设第$latex i$个人左手为L[i], 右手为R[i], 国王为第0个人, 则:

考虑对一对临项$latex i$, $latex i+1$顺序的决策.

交换顺序前$latex coin[i]=\prod_{j=0}^{i-1} L[j] \div R[i]$, $latex coin[i+1]=\prod_{j=0}^{i} L[j] \div R[i+1]$;

交换后$latex coin[i]=\prod_{j=0}^{i-1} L[j]\times L[i+1] \div R[i]$, $latex coin[i+1]=\prod_{j=0}^{i-1} L[j] \div R[i+1]$

($latex coin[i]$表示原第i位大臣所得金币)

提取公因式$latex \prod_{j=0}^{i-1}L[j]$, 所以现在要比较$latex max(1\div R[i], L[i]\div R[i+1])$与 $latex max(L[i+1]\div R[i], 1\div R[i+1])$

同乘$latex R[i]\times R[i+1]$得$latex max(R[i+1], L[i]\times R[i])$与 $latex max(L[i+1]\times R[i+1], R[i])$

又有$latex R[i]<= L[i]\times R[i]$与 $latex R[i+1]<=L[i+1]\times R[i+1]$

所以当$latex L[i]\times R[i]<L[i+1]\times R[i+1]$时, 后者为$latex L[i+1]\times R[i+1]$, 不管前者取哪个后者都更大,  也就是交换后结果变差, 所以交换前更优.

所以任意$latex i$都满足$latex L[i]\times R[i]<L[i+1]\times R[i+1]$时最优, 即按乘积升序排列.

赞(0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址