P3092 [USACO13NOV]No Change G

就是给第 i i i个硬币分配位置 p o s i pos_i posi​,使得 c o i n [ i ] > = ( s u m [ p o s i ] − s u m [ p o s i − 1 ] ) coin[i]>=(sum[pos_i]-sum[pos_{i-1}]) coin[i]>=(sum[posi​]−sum[posi−1​]) 问你怎么分配硬币的位置,硬币的价值和最小的情况下完成上述任务. 考虑下二分答案,二分出硬币价值和 m i d mid mid.之后,二进制枚举每一个方案 s t st st,看这些方案是否能凑成上述条件. 有点不太会了,参考下别人的思路了,上面都是我没做出来瞎勾八想的 用 d p ( s t ) dp(st) dp(st)表示二进制状态 s t st st最远到达哪个点.再记录这个状态下的消费 c o s t ( s t ) cost(st) cost(st) 考虑这个 s t st st的状态如何到达,考虑去掉某一位原本在 s t st st是1的位,更改为0,表示从这个旧的状态 s t 1 st1 st1转移过来,使用硬币 i i i,那么之前的 s t 1 st1 st1,已经购买了前 d p ( s t 1 ) dp(st1) dp(st1)个物品,对于当前要用的物品,假设当前价值为 v v v,我们希望尽快地找到最大 r r r,满足 s u m [ r ] − s u m [ d p [ s t 1 ] ] < = v sum[r]-sum[dp[st1]]