原文网址 original article URL : http://blog.163.com/eden_284914869/blog/static/252246078201691042223315/
这次比赛是我这个蒟蒻第一次进前300,非常开心!
这次比赛中,我觉得,最有价值的一道题是E题。
原题网址:http://codeforces.me/contest/724/problem/E
题目大意:在数轴上从左到右n个城市,在每个城市可以生产pi个产品,可以卖掉si个产品,你也可以把货物从i城市运送到j城市,但要满足i<j,且从i到j最多运送c份产品。你可以在数轴上走来走去,这倒无所谓。问你最多能卖掉多少产品。
我们构造这样一个网络流模型:

要求的是起点到终点的最大流,即最小割。
我们来验证这样一个猜想,
假定集合A,集合B,A∪B={1, 2, 3, ... , n},A∩B=∅。
那么答案ans = ∑(i∈A) pi + ∑(i∈B) si + ∑(i∈A, j∈B, j<i) c
大意,如上图,在上面选择 起点到任意城市的边 割掉,在下面选择 其他城市到终点的边割掉。
那么上面还剩下某些城市与起点相连,下面还剩下某些城市与终点相连,在这些城市中,连接起点的城市j 可能会到 连接终点的城市i,那么也要把这条边删去,代价是c。
证明(我懒得写了,可以自己找一下反例(找不到的))
于是如上图,分割方案可能是,

把橘红色的边删去即可。
那么我们来想一下怎么dp呢?
我们先枚举位置,从城市1到城市n,
再枚举j,j为起点在当前位置之前有多少条边连着城市且没有被割掉。
我们的dp方程为
当前位置删掉连接终点的边,setmin( dp[i][j+1], dp[i-1][j] + s[i] ) (这很明显)
当前位置删掉连接起点的边,那么连接终点的边就多了一条,所以我们还要删去 j 条容量为c的边。
即setmin( dp[i][j], dp[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);
}



