可以在 cnblog 中阅读。
题意
有 \(n\) 座城市，第 \(i\) 座城市生产了 \(p_i\) 件货物，最多可以出售 \(s_i\) 件货物，编号小的城市可以向编号大的城市运输至多 \(c\) 件货物，问最多能出售多少货物。
\(n \le 10^4\)。
分析
乍一看是一个网络流问题，可以这样建图，令 \(S\) 为源点 \(T\) 为汇点：
\[S \xrightarrow{p_i} i \xrightarrow{s_i} T \]\[i \xrightarrow{c} j (i < j) \]然后跑一个最大流就可以。但这样建边第二类就会有 \(O(n^2)\) 条边，寄。
模拟费用流就是应对这样的情况的。我们把最大流问题转换为最小割问题，然后考虑使用 DP 求解。
令 \(f(i,j)\) 表示前 \(i\) 个点，\(j\) 个点与 \(S\) 的连边未断开，注意到 \((S,i)\) 与 \((i,T)\) 必断其一，则有转移：
\[f(i,j) = \min \begin{cases} f(i-1,j) + p_i + c \times j \\ f(i-1,j-1) + s_i \end{cases}\]分别表示：
- 断开 \((S,i)\) 需要断开与前面所有未断开与 \(S\) 连边的点的连边；
- 断开 \((i,T)\)。
时间复杂度 \(O(n^2)\)。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
const int N=1e5+5;
int n,c;
int s[N],p[N];
int f[N];
signed main()
{
IOS;
cin>>n>>c;
for(int i=1;i<=n;i++) cin>>p[i];
for(int i=1;i<=n;i++) cin>>s[i];
for(int i=1;i<=n;i++)
{
f[i]=f[i-1]+s[i];
for(int j=i-1;j>=1;j--)
f[j]=min(f[j]+c*j+p[i],f[j-1]+s[i]);
f[0]+=p[i];
}
int ans=1e16;
for(int i=0;i<=n;i++) ans=min(ans,f[i]);
cout<<ans<<endl;
return 0;
}