Description
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 p i units of goods. No more than s i 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.
Input
The first line of the input contains two integers n and c (1 ≤ n ≤ 10 000 , 0 ≤ c ≤ 10 9 ) — the number of cities and the maximum amount of goods for a single transportation.
The second line contains n integers p i ( 0 ≤ p i ≤ 10 9 ) — the number of units of goods that were produced in each city.
The third line of input contains n integers s i ( 0 ≤ s i ≤ 10 9 ) — the number of units of goods that can be sold in each city.
Output
Print the maximum total number of produced goods that can be sold in all cities after a sequence of transportations.
Solution
Build a network of the following form: The network will consist of n + 2 vertices, the source located at the node with the number n + 1 and the sink at the node with the number n + 2 . For each node i such that 1 ≤ i ≤ n add the arc (n + 1, i) with a capacity p i and arc (i, n + 2) with capacity s i . Also, for each pair of nodes i and j such that 1 ≤ i < j ≤ n , add the arc (i, j) with capacity m.
The value of the maximum flow in this network is the answer to the problem. Since the network contains O(n 2 ) arcs, the usual flow search algorithms is not applicable here.
Instead, we will find a capacity of the minimal cut in this network. The cut in this case is a partition of the set of all nodes from 1 to n + 2 into two parts. Let A be the part that contains the source and
— all other nodes. Then the capacity of the cut is equal to
.
Capacity of the minimal cut can be found using the following dynamic programming: cut(i, j) will be the minimum capacity of the cut, which was built on the first i nodes, such that the set A contains exactly j nodes other than the source. It is easy to get the formula for this dynamic: cut(i, j) = min(cut(i − 1, j − 1) + s i , cut(i − 1, j) + p i + j ∗ c) .
The answer to the problem can be obtained as min j = 0, n cut(n, j) .
The resulting complexity of this solution is O(n 2 ) . To fit in memory limit you should store only two consecutive rows during the computation of the dynamic.
翻譯一下就是考慮網絡流：
1. S to i : p i
2. i to T : s i
3. i to j : c (i<j)
最大流就是答案，但直接跑是 O(n 2 ) 級别的邊，肯定爆炸。考慮到這個網絡的特殊性，同時考慮到最大流等于最小割。設計狀态 f[i][j] 表示對于前 i 個點中有 j 個點分到了 S 集合的最小割邊代價，轉移為 f[i][j]=min(f[i−1][j−1]+s i ,f[i−1][j]+p i +j∗c) ，轉移時間複雜度 O(n 2 ) ，空間上需要滾動一下。
Source
http://codeforces.com/contest/724/problem/E