P1912 [NOI2009] 诗人小G 题解

标签：infty le 题解 P1912 big NOI2009

我们设 \(s_i\) 表示前 \(i\) 个句子的长度之和，这样就有 dp

\[f_i = \min_{j < i} \big\{f_j + |s_i - s_j + i - j - 1 - L|^P\big\} \]

我们设 \(w(l, r) = |s_r - s_l + r - l - 1 - L|^ P\)，如果 \(w\) 满足四边形不等式，则原 dp 具有决策单调性。

设 \(u = (s_i + i) - (s_j + j ) - (1 + L)\), \(v = (s_i + i) - (s_j + j + 1 + a_j) - (1 + L)\)。

那么我们证明 \((j < j + 1 < i < i + 1 )\)

\[w(j, i) + w(j + 1, i + 1) \le w(j, i + 1) + w(j + 1, i) \]

等价于证明

\[|u|^P + |v + a_i+1|^P \le |v|^P +|u+a_i+1|^P \\ |u|^P - |u + a_i+1|^P \le |v|^P - |v + a_i+1| \]

因为 \(a_j > 0\)，所以 \(u > v\)，如果我们设 \(h(x) =|x|^P - |x+z|^P\)，那么如果 \(h(x)\) 单调不增，则原命题成立。

我们对绝对值进行讨论。

• 当 \(x \in [0, \infty)\) 时

\[h(x)=x^P - (x+z)^P \\ h'(x) = Px^{P - 1} - P(x + z)^{P - 1} \\ h'(x) = P[x^{P - 1} - (x+z)^{P - 1}] \\ h'(x) = P[x^{P - 1} - \sum_{i = 0}^{P - 1}x^{P - 1 - i}z^i] \\ h'(x) = P[-\sum_{i = 1}^{P - 1}x^{P - 1 - i}z^i] \\ \]

因为　\(P > 0, x > 0, z > 0\)，所以 \(h(x) \le 0, \Box\)

• 当 \(x \in (-\infty, 0)\) 时

注意到此时 \(P\) 的取值会影响到 \(x^P\) 的正负（实际上是 \(h'(x)\) 中 \(x^{P - 1}\) 的正负），所以需要对 \(P\) 的奇偶性进行讨论。

• • 当 \(P\) 为偶数时

    证明过程完全
    

标签：infty,le,题解,P1912,big,NOI2009
From： https://www.cnblogs.com/Rainsheep/p/18309243