链接：https://www.luogu.com.cn/problem/CF724E
题目描述：有\(n\)个城市，每个城市生产了\(p_{i}\)个货物，最多可以卖掉\(s_{i}\)个货物。对于每两个城市\((i,j)\)，如果\(i<j\)，则可以最多从\(i\)运送\(c\)个货物到\(j\)。注意不能反向运送，却可以在多个城市之间送来送去。求经过运输后，最多能卖掉多少个货物。
题解；看完题目先想\(dp\),但由于无法记录每一个货物的状态，不好转移。
"无法记录每一个货物的状态"\(?\)，可以想到网络流。
考虑建出最大流模型，连这么几条边：
\((s,i,p_{i})\)
\((i,t,s_{i})\)
\((i,j,c)\)(\(i<=j\))
那么我们又可以把它看作最小割：
令\(dp_{i,j}\)表示前\(i\)个点，有\(j\)个与\(s\)仍相连的方案数，那么有两种情况：
\(1.\)断\((i,t)\),仅需\(s_{i}\)代价
\(2\).断\((s,i)\),需\(p_{i}+j\times c\)的代价，因为还有流\(s->p->i->t\)（\(p<i\))。
这样就可以\(O(n^2)\)了
#include<iostream>
#include<cstdio>
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9')
c=getchar();
while ('0'<=c&&c<='9')
{
sum=sum*10+c-'0';
c=getchar();
}
return sum;
}
long long minn=1e18,n,c,a[10001],b[10001],dp[2][10001],op;
int main()
{
n=read(),c=read();
for (int i=1;i<=n;++i)
a[i]=read();
for (int i=1;i<=n;++i)
b[i]=read();
for (int i=1;i<=n;++i)
dp[0][i]=1e18;
for (int i=1;i<=n;++i)
{
op^=1;
for (int j=0;j<=n;++j)
dp[op][j]=1e18;
for (int j=1;j<=n;++j)
dp[op][j]=min(dp[op][j],dp[op^1][j-1]+b[i]);
for (int j=0;j<=n;++j)
dp[op][j]=min(dp[op][j],dp[op^1][j]+j*c+a[i]);
}
for (int j=0;j<=n;++j)
minn=min(minn,dp[op][j]);
printf("%lld\n",minn);
return 0;
}