题意：

　　小明升任了 CF 国的大总管，他管辖的 n 个城市，编号为 1..n。每个城市生产了 pi 个货物，限制最多可以卖掉 si 个货物。对于每两个城市 i, j，如果 i < j，则可以最多从 i 运送 c 个货物到 j。注意不能反向运送，却可以在多个城市之间送来送去。现在小明想知道，经过运输后，最多能卖掉多少个货物。

 

分析：

　　我们按照题意试试建图跑网络流？

　　虚构源点和汇点，源点向每个城市连边容量为pi，每个城市向汇点连边容量为si，对于所有编号i<j的城市，i向j连边容量为c，跑最大流？

　　可是数据范围决定了，肯定开不下，所以我们得另寻他法。

　　最大流=最小割

　　而且题目里的限制条件非常好，我们可以直接dp，设f[i][j]表示考虑前i个城市，将其中j个城市分到离源点近的集合，这些点的最小割是多少。我们只需要枚举对于一个点分在哪个集合就好了，而且可以开的下滚动数组，时间复杂度也是可以的。

代码：

 

1 #include
      
        2 #define ll long long 3 using namespace std; 4 const int N=10005; 5 const ll inf=1e14;int n,c; 6 ll f[2][N],p[N],s[N],ans=0,mn; 7 int main(){ 8     scanf("%d%d",&n,&c); 9     for(int i=1;i<=n;i++)10     scanf("%lld",&p[i]);11     for(int i=1;i<=n;i++)12     scanf("%lld",&s[i]);13     for(int i=1;i<=n;i++){14         ans+=min(s[i],p[i]);15         int x=i&1,y=(i-1)&1;16         for(int j=0;j<=i;j++){17             f[x][j]=inf;18             if(p[i]>s[i]){
    //供过于求19                 if(j!=i) f[x][j]=min(f[x][j],20                 f[y][j]+p[i]-s[i]+(ll)j*c);21                 if(j) f[x][j]=min(f[x][j],22                 f[y][j-1]);23             } else{
    //供不应求或自产自销24                 if(j!=i) f[x][j]=min(f[x][j],25                 f[y][j]+(ll)j*c);26                 if(j) f[x][j]=min(f[x][j],27                 f[y][j-1]+s[i]-p[i]);28             }29         }30     } mn=f[n&1][0];31     for(int i=1;i<=n;i++) mn=min(mn,f[n&1][i]);32     printf("%lld\n",mn+ans);33 }