题解 CF724E 【Goods transportation】

2020-04-28 22:23:59


可能更好的阅读体验

容易想到一个网络流做法,即源点向每个点连容量为 $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;
}