一道水题，P5017 摆渡车。

我这个dp方程和第一篇题解类似，但是搞斜率优化的时候出现了问题。

假设有决策$j$优于决策$k\;(k<j)$，则

$$f_j+(cnt_i-cnt_j)\times i-(sum_i-sum_j)<f_k+(cnt_i-cnt_k)\times i-(sum_i-sum_k)$$ $$f_j+sum_j-cnt_j\times i<f_k+sum_k-cnt_k\times i$$ $$\frac{f_j+sum_j-f_k-sum_k}{cnt_j-cnt_k}<i$$

于是乎和题解的完全不一样了。

按照代码我也写了一份：

//本人已AC，此代码完全为了测试一个另外的斜率优化 
#include <cstdio>
#include <algorithm>

const int maxT = 4000105;

int n, m, t, ti, ans = 1e9, l = 1, r, cnt[maxT], sum[maxT], q[maxT], f[maxT];

inline double getSlope(int u, int v) { return (double) (f[v] + sum[v] - f[u] - sum[u]) / (cnt[u] == cnt[v] ? 1e-9 : cnt[v] - cnt[u]); }

int main() 
{
	
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; i++) {
        scanf("%d", &ti); t = std::max(t, ti);
        cnt[ti]++; sum[ti] += ti;
    }
    
    for (int i = 1; i < t + m; i++) { cnt[i] += cnt[i - 1]; sum[i] += sum[i - 1]; } // 前缀和.
    
    for (int i = 0; i < t + m; i++) {
        if (i - m >= 0) {
        	while (l < r && getSlope(q[r - 1], q[r]) < i) { r--; }
        	q[++r] = i; // 把可能成为最优解的推入队列. 
        }
        
    	while (l < r && getSlope(q[l], q[l + 1]) > i) { l++; } // 把不可能成为最优解的弹出队列. 
        f[i] = cnt[i] * i - sum[i]; // 特判边界情况.
        if (l <= r) { f[i] = std::min(f[i], f[q[l]] + (cnt[i] - cnt[q[l]]) * i - (sum[i] - sum[q[l]])); } // 斜率优化转移. 
    }
    
    for (int i = t; i < t + m; i++) { ans = std::min(ans, f[i]); }
    
    printf("%d\n", ans);
    return 0;
}

然鹅我这样是错的。

题解里面有个什么i-m，我不太理解其中的含义。并且按照之前做斜率优化的经验，我并不觉得我的做法有什么问题？