AT_abc374_f Shipping

原题链接

不难发现一次发出一定是 \(a_i+kx,k\in \mathbb{Z}\) 的时刻，因为你一次发出不然就是可以发出抓紧发出，否则肯定是要等到下一次有新包裹要发出再发出，不然你中间等待没意义。也就是说相当于从一个时刻开始连续发送若干次。

设 \(f_{i,j}\) 为在第 \(i\) 个包裹到达时，总共有 \(j\) 个包裹还没发出时，已发出包裹的发出时间和的最小值。

转移时枚举 \(i,j\)，再不断发出包裹，直至没有包裹要发出。每次发出一些包裹，然后时间 \(+x\)，再将这 \(x\) 时间内的新到达的包裹数加上，转移到下一个包裹到达时。总时间复杂度 \(O(n^3)\)。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
#define int long long
#define ll long long
using namespace std;
const int MAXN=110,INF=1e15;
int n,k,x,t[MAXN],f[MAXN][MAXN],ans;
signed main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
    memset(f,0x3f3f3f,sizeof(f));
    cin>>n>>k>>x;f[0][0]=0;
    for(int i=1;i<=n;++i) cin>>t[i],ans-=t[i];
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<i;++j) f[i][j]=min(f[i][j],f[i-1][j]);
        for(int j=i;j;--j) f[i][j]=f[i][j-1];f[i][0]=INF;
        for(int j=1;j<=i;++j)
        {
            int now=j,tim=t[i],sum=0,k=i+1;
            while(now)
            {
                int cur=min(now,::k);
                sum+=cur*tim,now-=cur,tim+=::x;
                for(;k<=n&&t[k]<tim;++k) ++now;
                f[k][now]=min(f[k][now],f[i][j]+sum);
            }
        }
    }
    cout<<(ans+f[n+1][0])<<'\n';
}