传送门
一道神奇的dp题。
这题的决策单调性优化跟普通的不同。
首先发现这道题只跟r−lr-lr−l有关。
然后定义状态f[i][j]f[i][j]f[i][j]表示猜范围为[L,L+i−1][L,L+i-1][L,L+i−1]的数有jjj次报警机会所需的最小代价。
那么有：
f[i][j]=minf[i][j]=minf[i][j]=min{max(f[k][j],f[i−k][j−1]+1)max(f[k][j],f[i-k][j-1]+1)max(f[k][j],f[i−k][j−1]+1)}，然后打表可以发现对于同一个jjj，kkk随着iii单增
然后就做完了。
代码