Codeforces

Luogu

分析

容易想到一个网络流做法，即源点向每个点连容量为 $p_i$ 的边，每个点向汇点连容量为 $s_i$ 的边，每个点向编号比它大的点连容量为 $c$ 的边，然后求最大流即可。

发现最大流不好求，而图比较特殊，可以考虑 DP 求最小割。

设 $dp_{i,j}$ 表示前 $i$ 个点有 $j$ 个点和源点相连的最小割。转移这样考虑：如果 $i$ 与源点相连，则断掉连向汇点的边即可，代价为 $s_i$；如果 $i$ 与汇点相连，则断掉源点连来的边和前面与源点相连的边连来的边即可，代价为 $j\times c+p_i$。从而不难得到状态转移方程
$$
dp_{i,j}=\min\{dp_{i-1,j}+j\times c+p_i,dp_{i-1,j-1}+s_i\}
$$
答案即为 $\min_{i=0}^n dp_{n,i}$。实现时需要滚动数组。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10000+10;

int n,c,p[N],s[N];
ll dp[2][N];

int main() {
    n=read(),c=read();
    for (int i=1;i<=n;++i) p[i]=read();
    for (int i=1;i<=n;++i) s[i]=read();
    for (int i=1;i<=n;++i) {
        int now=i&1,pre=now^1;
        memset(dp[now],0x3f,sizeof(dp[now]));
        dp[now][0]=dp[pre][0]+p[i];
        for (int j=1;j<=i;++j)
            dp[now][j]=min(dp[pre][j]+p[i]+1ll*c*j,dp[pre][j-1]+s[i]);
    }
    ll ans=2e18;
    for (int i=0;i<=n;++i) ans=min(ans,dp[n&1][i]);
    printf("%lld\n",ans);
    return 0;
}