照惯例CF的题不放原题链接。。。
题意：一个序列上有n个点，每个点有权值pi和si。表示这个点一开始有pi个物品，最多可以卖出si个物品，每个点都可以把物品向编号更大的点运输，但是对于i < j的任意点对(i, j)最多从i到j运c个物品。求最多能卖出多少个物品。
题解：
如果不考虑数据范围的话，可以直接用网络流建图。s向每个点连流量为pi的边，表示一开始有pi的流量，每个点i向满足i < j的点j连流量为c的边，表示最多运送c个物品，每个点向t连流量为si的边，表示最多可以卖si个物品。
最大流即为答案。
但是这题数据范围过大，无法用网络流跑过，观察到这个图比较特殊，即如果我们知道了哪些点属于S集合(S在残余网络中可以到达的点)，哪些点属于T集合，就可以直接算出最小割。
即$ans = \sum_{i \in S}{s_{i}} + \sum_{i \in T}{p_{i}} + \sum_{i \in S}\sum_{j \in T}{c}$
解释一下为什么是这样，应该是比较好理解的，从最小割这个角度来理解。
如果一个点属于S，那么它肯定要断开与t的边，所以加上$s_{i}$,
如果一个点属于T，那么它肯定要断开与s的边，所以加上$p_{i}$,
如果一个点属于S，另一个点属于T，那么这两个点之间的边肯定要断开。
因此我们设f[i][j]表示前i个点有j个属于S集的最小代价。
那么如果这个点i我们划分到S集合里面，我们就加上$s_{i}$的代价。
否则加上$p[i] + j \cdot c$的代价，$j \cdot c$表示这个点要与之前被划分到S集合里面的j个点都断开联系，因为边权都是c，所以代价就是$j \cdot c$.
转移的时候注意一下j从0开始枚举。
#include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 10010
#define LL long long int n;
LL c, ans = 1e18;
LL f[][AC], s[AC], p[AC]; inline int read()
{
int x = ;char c = getchar();
while(c > '' || c < '') c = getchar();
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x;
} inline void upmin(LL &a, LL b){
if(b < a) a = b;
} void pre()
{
n = read(), c = read();
for(R i = ; i <= n; i ++) p[i] = read();
for(R i = ; i <= n; i ++) s[i] = read();
} void work()
{
int now = ;
for(R i = ; i <= n; i ++)
{
now ^= ;
memset(f[now], , sizeof(f[now]));
for(R j = ; j <= i; j ++)
if(!j) f[now][j] = f[now ^ ][j] + p[i];
else f[now][j] = min(f[now ^ ][j] + p[i] + j * c, f[now ^ ][j - ] + s[i]);
}
for(R i = ; i <= n; i ++) upmin(ans, f[now][i]);
printf("%lld\n", ans);
} int main()
{
freopen("in.in", "r", stdin);
pre();
work();
fclose(stdin);
return ;
}
