一些闲话

原题传送门、双倍经验，这两题不是一模一样的吗？甚至输入输出都没改？？？

形象化题意

给定两个正整数 $n$ 和 $m$，以及一个长度为 $n$ 的数组 $a$，$a_i$ 为数轴上一点。请在数轴上求出若干个节点，使得 $a_i$ 到后面第一个节点的距离和最少

思路

一道明显的 dp 题。我们设 $dp_i$ 表示第 $i$ 个时刻最少的距离和。我们若设 $j$ 为上个节点的位置，显然需要 $0 \le j \le i-m$（$j=0$ 表示 $i$ 是第一个节点），此时 $dp_i= \min _{j=0}^{i-m}(dp_j+\sum_{k=1}^n(i-a_k) \times [j < a_k \le i])$。为了方便计算，我们设 $c_i$ 为时刻 $i$ 前所有点的时间的前缀和，$s_i$ 为时刻 $i$ 前点的个数。化简状态转移方程为 $dp_i= \min _{j=0}^{i-m}(dp_j+(s_i-s_j)\times i-(c_i-c_j))$。此时如果暴力转移，复杂度为 $O(\max(a_i)^2)$。成功拿下 50 pts。

#include <bits/stdc++.h>
#define ll long long
#define U unsigned
#define ss size()
using namespace std;
ll n,m,t,s[4100005],c[4100005],maxn,minn,dp[4100005];
int main() {
	cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        cin>>t;
        s[t]++;
        c[t]+=t;
        maxn=max(maxn,t);
    }//输入
    n=maxn+m;//往返还要时间
    for(ll i=1;i<n;i++){
        s[i]+=s[i-1];
        c[i]+=c[i-1];
    }//计算前缀和
    memset(dp,0x3f,sizeof dp);
    for(int i=0;i<m;i++)dp[i]=i*s[i]-c[i];//不能从前面转移
    minn=1e12;
    for(ll i=m;i<n;i++){
        for(ll j=0;j<=i-m;j++)dp[i]=min(dp[i],dp[j]+(s[i]-s[j])*i-(c[i]-c[j]));//暴力转移
        if(i>=maxn)minn=min(minn,dp[i]);//记录
    }
    cout<<minn;//输出
	return 0;
}

如何优化呢？我们再次化简状态转移方程，得到 $dp_i= \min _{j=0}^{i-m}(dp_j+s_i\times i-s_j\times i-c_i+c_j)$。观察式子，仅有 $s_j\times i$ 一项同时与 $i$、$j$ 相关。考虑斜率优化：设 $j_0$ 为最优状态的 $j$，变形状态转移方程为 $dp_{j_0}+c_{j_0}=(dp_i-s_i\times i+c_i)+s_{j_0}\times i$（此处式子变化较大，建议自己推一下）。这是不是很像一次函数 $y=k\times x+b$？！令 $y=dp_{j_0}+c_{j_0}$，$x=s_{j_0}$，$k=i$，$b=dp_i-s_i\times i+c_i$，所以当 $i$ 增大时，斜率 $k$ 也增大，则若截距 $b$ 最小时，$dp_i$ 最小。用单调队列维护凹壳就可以 $O(1)$ 转移了！所有总复杂度为 $O(n)$。

#include <bits/stdc++.h>
#define ll long long
#define U unsigned
#define ss size()
using namespace std;
ll n,m,t,s[4100005],c[4100005],maxn,minn,dp[4100005],j,X,Y,K,B;
struct node{
    ll x,y,i;
};
deque<node>q;//记录凹壳
double cross(node a,node b){
    if(a.x==b.x)return (a.y-b.y)/(1e-9);
    return (a.y-b.y)*1.0/(a.x-b.x);
}//求斜率
int main() {
	cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        cin>>t;
        s[t]++;
        c[t]+=t;
        maxn=max(maxn,t);
    }//输入
    n=maxn+m;//往返还要时间
    for(ll i=1;i<n;i++){
        s[i]+=s[i-1];
        c[i]+=c[i-1];
    }//计算前缀和
    memset(dp,0x3f,sizeof dp);
    for(int i=0;i<m;i++)dp[i]=i*s[i]-c[i];//不能从前面转移
    minn=1e12;
    for(ll i=m;i<n;i++){
        j=i-m;
        X=s[j];
        Y=dp[j]+c[j];
        while(q.ss>=2 && cross((node){X,Y,j},q[q.ss-1])<=cross(q[q.ss-1],q[q.ss-2]))q.pop_back();//出现凸壳，不断删除末节点直到凸壳消失
        q.push_back((node){X,Y,j});//插入新节点
        while(q.ss>=2 && cross(q[1],q[0])<=i)q.pop_front();//斜率过小，无用点删除
        j=q[0].i;
        dp[i]=dp[j]+(s[i]-s[j])*i-(c[i]-c[j]);//更新
        if(i>=maxn)minn=min(minn,dp[i]);//记录
    }
    cout<<minn;//输出
	return 0;
}

后话

这篇题解写的很详细，真的累死本蒟蒻了。

E54 斜率优化DP [NOIP2018 普及组] 摆渡车

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=510, M=110, T=4e6+M+10;
LL t[N], cnt[T], sum[T], f[T];
int main()
{
    int n, m;scanf("%d%d", &n, &m); 
    memset(cnt, 0, sizeof(cnt)); 
    memset(sum, 0, sizeof(sum));
    LL mxt=0;
    for(int i=1; i<=n; i++) 
    {
        scanf("%lld", &t[i]); mxt=max(mxt, t[i]);
        cnt[t[i]]++, sum[t[i]]+=t[i];
    }
    mxt+=m; 
    for(int i=1; i<=mxt; i++) cnt[i]+=cnt[i-1], sum[i]+=sum[i-1];
    memset(f, 0x7f, sizeof(f)); f[0]=0;
    for(int i=1; i<=mxt; i++) 
    {
        f[i]=cnt[i]*i-sum[i];
        for(int j=max(0, i-2*m); j<=i-m; j++)
        {
            f[i]=min(f[i], f[j]+(cnt[i]-cnt[j])*i-(sum[i]-sum[j]));
        }
    }
    LL ans=1e18;for(int i=mxt-m; i<mxt; i++) ans=min(ans, f[i]);
    printf("%lld\n", ans);
    return 0;
}