[codeforces724E]Goods transportation
试题描述
There are n cities located along the one-way road. Cities are numbered from 1 to n in the direction of the road.
The i-th city had produced pi units of goods. No more than si units of goods can be sold in the i-th city.
For each pair of cities i and j such that 1 ≤ i < j ≤ n you can no more than once transport no more than c units of goods from the city i to the city j. Note that goods can only be transported from a city with a lesser index to the city with a larger index. You can transport goods between cities in any order.
Determine the maximum number of produced goods that can be sold in total in all the cities after a sequence of transportations.
输入
The first line of the input contains two integers n and c (1 ≤ n ≤ 10 000, 0 ≤ c ≤ 109) — the number of cities and the maximum amount of goods for a single transportation.
The second line contains n integers pi (0 ≤ pi ≤ 109) — the number of units of goods that were produced in each city.
The third line of input contains n integers si (0 ≤ si ≤ 109) — the number of units of goods that can be sold in each city.
输出
Print the maximum total number of produced goods that can be sold in all cities after a sequence of transportations.
输入示例
4 3 13 10 7 4 4 7 10 13
输出示例
34
数据规模及约定
见“输入”
题解
这显然是一个最大流模型，从源点向每一个城市连一条容量为 pi 的单向边，从每个城市向汇点连一条容量为 si 的单向边，然后每个城市向编号比它大的所有城市连一条容量为 c 的单向边。
然而最多有 10002 个点，50015000 条边，时间暂且不考虑，每条边需要有反向弧，并且每条弧至少需要存 2 个 int（边的终点和边的剩余流量），对于 256MB 的限制来说太大了。
然而这题有一个比较妙的办法，由于建图的特殊性，我们可以转化成最小割之后 dp，设 f(i, j) 表示前 i 个点中 j 个点属于 S 集合的最小割是多少。
第一步：先把从源点到节点 i 再到汇点的流量先耗尽，于是残量网络就变成了这个样子：
若 pi > si，则从源点向 i 连一条 pi - si 的边；
若 pi < si，则从 i 向汇点连一条 si - pi 的边；
若 0 < i < j < n + 1，则从 i 向 j 连一条 c 的边。
第二步：考虑上面的 dp 如何转移，枚举当前点属于 S 集还是 T 集。我很懒，不想再写了，转移方程不妨留给读者思考吧。。。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std;
const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
if(Head == Tail) {
int l = fread(buffer, 1, BufferSize, stdin);
Tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }
return x * f;
}
#define maxn 10010
#define oo (1ll << 60)
#define LL long long
LL f[2][maxn];
int n, C, P[maxn], S[maxn];
int main() {
n = read(); C = read();
for(int i = 1; i <= n; i++) P[i] = read();
for(int i = 1; i <= n; i++) S[i] = read();
for(int i = 0; i < 2; i++)
for(int j = 0; j <= n; j++)
f[i][j] = oo;
f[0][0] = 0;
LL base = 0; bool cur = 1;
for(int i = 1; i <= n; i++, cur ^= 1) {
base += min(S[i], P[i]);
for(int j = 0; j <= n; j++) f[cur][j] = oo;
for(int j = 0; j <= i; j++) {
if(S[i] > P[i]) {
if(j && f[cur^1][j-1] < oo) f[cur][j] = min(f[cur][j], f[cur^1][j-1] + S[i] - P[i]);
if(f[cur^1][j] < oo) f[cur][j] = min(f[cur][j], f[cur^1][j] + (LL)j * C);
}
else {
if(j && f[cur^1][j-1] < oo) f[cur][j] = min(f[cur][j], f[cur^1][j-1]);
if(f[cur^1][j] < oo) f[cur][j] = min(f[cur][j], f[cur^1][j] + P[i] - S[i] + (LL)j * C);
}
}
}
LL tmp = oo;
for(int i = 0; i <= n; i++) tmp = min(tmp, f[cur^1][i]);
printf("%I64d
", base + tmp);
return 0;
}