codeforces 724E
Разница между en1 и en2, 4 символ(ов) изменены
**原文网址** original article **URL** : [http://blog.163.com/eden_284914869/blog/static/252246078201691042223315/](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份产品。你可以在数轴上走来走去,这倒无所谓。问你最多能卖掉多少产品。↵
↵
我们构造这样一个网络流模型:↵
↵
![ ](http://codeforces.me/predownloaded/2a/9a/2a9adcc963f4fff7db9d691a937899a5c1f6ddb3.png)↵
↵
要求的是起点到终点的最大流,即最小割。↵
↵
我们来验证这样一个猜想,↵
↵
假定集合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。↵
↵
证明(我懒得写了,可以自己找一下反例(找不到的))↵
↵
于是如上图,分割方案可能是,↵
↵
![ ](http://codeforces.me/predownloaded/44/e7/44e70be7475ac09164a2bc220b103e5d04dccf37.png)↵
↵
把橘红色的边删去即可。↵
↵
那么我们来想一下怎么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);↵
}↵
↵
~~~~~

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский VPigeonKing 2016-10-10 13:42:34 22
en7 Английский VPigeonKing 2016-10-10 13:34:51 4
en6 Английский VPigeonKing 2016-10-10 13:34:36 174
en5 Английский VPigeonKing 2016-10-10 13:29:00 9
en4 Английский VPigeonKing 2016-10-10 13:28:06 685
en3 Английский VPigeonKing 2016-10-10 13:19:21 1077
en2 Английский VPigeonKing 2016-10-10 13:02:40 4 Tiny change: ' , n},A∩B= ? 。\n\n那么答案a' -> ' , n},A∩B=∅。\n\n那么答案a'
en1 Английский VPigeonKing 2016-10-10 12:23:30 2276 Initial revision (published)