↵
↵
这次比赛中,我觉得,最有价值的一道题是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 )↵
↵
真正的代码我们要用滚动数组。↵
↵
好了,现在发现这题是不是很神奇?!↵
↵
↵
来晒代码:↵
↵
~~~~~↵
#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);↵
}↵
↵
~~~~~



