题目描述

做法

首先晃眼一看：这不是网络流傻子题吗？

于是立刻建了个图跑最大流：

  1. 建立源点 $S$，向第 $i$ 个点建立一条容量为 $p_i$ 的边；

  2. 建立汇点 $T$，第 $i$ 个点向 $T$ 建立一条容量为 $s_i$ 的边；

  3. 对于所有的 $i<j$，由 $i$ 向 $j$ 建立一条容量为 $c$ 的边。

正当建完图打算交的时候，定睛一看：$n\le10000$，这不明摆着 TLE？

于是就需要另外一个方法：模拟网络流。

首先因为最大流等于最小割，于是原问题就变成了求原网络的最小割。

显然对于一种最小割，每个点要么属于 $S$ 所在的集合，要么属于 $T$ 所在的集合。

并且是由小的连向大的，所以无后效性。

于是令 $f_{i,j}$ 表示前 $i$ 个点中，有 $j$ 个点属于 $S$ 集合的最小割。

于是对于点 $i$，有两种方案：

  1. $i$ 属于 $S$ 集合，则割掉 $i$ 连向 $T$ 的边

  2. $i$ 属于 $T$ 集合，则割掉 $i$ 连向 $S$ 的边和连向下标小于 $i$ 的边。

故转移方程为：$f_{i,j}=\min(f_{i-1,j}+p_i+j\times c,f_{i-1,j-1}+s_i)$

空间开不下，要使用滚动数组。

代码

#include<cstring>
#include<iostream>
#define int long long
using namespace std;
int f[2][10005],n,a[10005],s[10005],c;
signed main()
{
    scanf("%lld%lld",&n,&c);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)scanf("%lld",&s[i]);
    for(int i=1;i<=n;i++)
    {
        memset(f[i&1],0x7f,sizeof(f[i&1]));
        f[i&1][0]=f[(i-1)&1][0]+a[i];
        for(int j=1;j<=i;j++)f[i&1][j]=min(f[(i-1)&1][j-1]+s[i],f[(i-1)&1][j]+a[i]+j*c);
    }
    int ans=2e18;
    for(int i=0;i<=n;i++)ans=min(ans,f[n&1][i]);
    printf("%lld",ans);
}