Algorithm: maximum flow, min-cut↵
↵
The network will consist of n + 2 vertices, ↵
↵
the source point located at the node with the number 0 and the sink at the node with the number n + 1. ↵
↵
For each node i such that 1 ≤ i ≤ n add the arc (0, i) with a capacity pi ↵
↵
and arc (i, n + 2) with capacity si.↵
↵
Also, for each pair of nodes i and j such that 1 ≤ i < j ≤ n, add the arc (i, j) with capacity c, ↵
↵
so that the answer is just the maximum flow of the network.↵
↵
but there are n^2/2 edges, so it's not available to get the answer of max-flow, you need to use dp to work out the min-cut, for the max-flow is equal to min-cut.↵
↵
define i as the position and j, j is on the left of position i, there are j cities connecting to the source.↵
↵
then↵
↵
f[i][j+1]=f[i-1][j]+s[i]↵
↵
f[i][j]=f[i-1][j]+p[i]+j*c↵
↵
**here is the code**:↵
↵
~~~~~↵
#include <cstdio>↵
#include <cstring>↵
#include <iostream>↵
#include <cmath>↵
#include <string>↵
#include <cstdlib>↵
#define longlongtype↵
using namespace std;↵
typedef long long LL;↵
#define ref(i,x,y)for(int i=x;i<=y;i++)↵
#define def(i,x,y)for(int i=x;i>=y;i--)↵
#ifdef longlongtype↵
typedef long long LL;↵
#define T LL↵
const T oo=1e16;↵
#endif↵
#ifdef inttype↵
#define T int↵
const T oo=2e9;↵
#endif↵
T max(T a,T b){return a>b?a:b;};↵
T min(T a,T b){return a<b?a:b;};↵
T gcd(T a,T b){return b?gcd(b,a%b):a;};↵
T read(){char c=getchar();T d=0,f=1;for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;for(;c>='0'&&c<='9';d=d*10+c-48,c=getchar());return d*f;}↵
T n,c,ans,a[10001],b[10001],f[10001];↵
int main()↵
{↵
n=read(),c=read();↵
ref(i,1,n)a[i]=read();↵
ref(i,1,n)b[i]=read();↵
ref(i,1,n)f[i]=oo;↵
ref(i,1,n)def(j,i-1,0)↵
{↵
f[j+1]=min(f[j+1],f[j]+b[i]);↵
f[j]=f[j]+a[i]+j*c;↵
}↵
ans=oo;↵
ref(i,0,n)ans=min(ans,f[i]);↵
printf("%I64d\n",ans);↵
}↵
↵
~~~~~
↵
The network will consist of n + 2 vertices, ↵
↵
the source point located at the node with the number 0 and the sink at the node with the number n + 1. ↵
↵
For each node i such that 1 ≤ i ≤ n add the arc (0, i) with a capacity pi ↵
↵
and arc (i, n + 2) with capacity si.↵
↵
Also, for each pair of nodes i and j such that 1 ≤ i < j ≤ n, add the arc (i, j) with capacity c, ↵
↵
so that the answer is just the maximum flow of the network.↵
↵
but there are n^2/2 edges, so it's not available to get the answer of max-flow, you need to use dp to work out the min-cut, for the max-flow is equal to min-cut.↵
↵
define i as the position and j, j is on the left of position i, there are j cities connecting to the source.↵
↵
then↵
↵
f[i][j+1]=f[i-1][j]+s[i]↵
↵
f[i][j]=f[i-1][j]+p[i]+j*c↵
↵
**here is the code**:↵
↵
~~~~~↵
#include <cstdio>↵
#include <cstring>↵
#include <iostream>↵
#include <cmath>↵
#include <string>↵
#include <cstdlib>↵
#define longlongtype↵
using namespace std;↵
typedef long long LL;↵
#define ref(i,x,y)for(int i=x;i<=y;i++)↵
#define def(i,x,y)for(int i=x;i>=y;i--)↵
#ifdef longlongtype↵
typedef long long LL;↵
#define T LL↵
const T oo=1e16;↵
#endif↵
#ifdef inttype↵
#define T int↵
const T oo=2e9;↵
#endif↵
T max(T a,T b){return a>b?a:b;};↵
T min(T a,T b){return a<b?a:b;};↵
T gcd(T a,T b){return b?gcd(b,a%b):a;};↵
T read(){char c=getchar();T d=0,f=1;for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;for(;c>='0'&&c<='9';d=d*10+c-48,c=getchar());return d*f;}↵
T n,c,ans,a[10001],b[10001],f[10001];↵
int main()↵
{↵
n=read(),c=read();↵
ref(i,1,n)a[i]=read();↵
ref(i,1,n)b[i]=read();↵
ref(i,1,n)f[i]=oo;↵
ref(i,1,n)def(j,i-1,0)↵
{↵
f[j+1]=min(f[j+1],f[j]+b[i]);↵
f[j]=f[j]+a[i]+j*c;↵
}↵
ans=oo;↵
ref(i,0,n)ans=min(ans,f[i]);↵
printf("%I64d\n",ans);↵
}↵
↵
~~~~~
