题目描述

一个餐厅在相继的 NN 天里,每天需用的餐巾数不尽相同。假设第 ii 天需要 r_iri块餐巾( i=1,2,...,N)。餐厅可以购买新的餐巾,每块餐巾的费用为 pp 分;或者把旧餐巾送到快洗部,洗一块需 m 天,其费用为 f 分;或者送到慢洗部,洗一块需 nn 天(n>mn>m),其费用为 ss 分(s<fs<f)。

每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。

试设计一个算法为餐厅合理地安排好 NN 天中餐巾使用计划,使总的花费最小。编程找出一个最佳餐巾使用计划。

输入格式

由标准输入提供输入数据。文件第 1 行有 1 个正整数 NN，代表要安排餐巾使用计划的天数。

接下来的一行是餐厅在相继的 NN 天里,每天需用的餐巾数。

最后一行包含5个正整数p,m,f,n,sp,m,f,n,s。pp 是每块新餐巾的费用; mm 是快洗部洗一块餐巾需用天数; ff 是快洗部洗一块餐巾需要的费用; nn 是慢洗部洗一块餐巾需用天数; ss 是慢洗部洗一块餐巾需要的费用。

输出格式

将餐厅在相继的 N 天里使用餐巾的最小总花费输出

输入输出样例

输入  
3
1 7 5 
11 2 2 3 1

输出 

134

说明/提示

N<=2000

ri<=10000000

p,f,s<=10000

时限4s

 

思路：

设每天需要ned[i]个餐巾。把每一天拆成早晨和晚上，s = 0为超级源点，t = 2 * n + 1为超级汇点。如下建图：

（1）s向每天晚上连边，每天晚上都会有当天剩下的脏餐巾，流量为ned[i]，费用为0

（2）每天早晨向t连边，每天早晨需要ned[i]个干净的餐巾，流量为ned[i]，费用为0

（3）每天晚上都可以把脏餐巾留到以后再洗，前一天晚上向第二天晚上连边，流量为inf，费用为0

（4）每天晚上可以把脏餐巾送去快洗部，向洗完的第一天早晨连边（判断一下能不能在n天前洗完），流量为inf，费用为f

（5）每天晚上可以把脏餐巾送去慢洗部，向洗完的第一天早晨连边（判断一下能不能在n天前洗完），流量为inf，费用为s

（6）s向每天早晨连边，表示可以买新餐巾，流量为inf，费用为p 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e4 + 10;
const int M = 5e5 + 10;
 
inline ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch)) {
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(isdigit(ch)) {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
 
struct Edge {
    ll to, next, cap, flow, cost;
}edge[M];
 
ll head[N], tot, pre[N], n, m, s, t, ned[N];
ll minCost, maxFlow, dis[N];
bool vis[N];
 
void init() {
    tot = 0;
    memset(head, -1, sizeof(head));
}
 
void addedge(ll u, ll v, ll cap, ll cost) { //cap流量 cost花费
    edge[tot].to = v;
    edge[tot].cap = cap;
    edge[tot].cost = cost;
    edge[tot].flow = 0;
    edge[tot].next = head[u];
    head[u] = tot++;
 
    edge[tot].to = u;
    edge[tot].cap = 0;
    edge[tot].cost = -cost;
    edge[tot].flow = 0;
    edge[tot].next = head[v];
    head[v] = tot++;
}
 
bool spfa(ll s, ll t) {
    queue<ll>q;
    for(ll i = 0; i < N; ++i) {
        dis[i] = inf;
        vis[i] = 0;
        pre[i] = -1;
    }
    dis[s] = 0;
    vis[s] = 1;
    q.push(s);
    while(!q.empty()) {
        ll u = q.front();
        q.pop();
        vis[u] = 0;
        for(ll i = head[u]; i != -1; i = edge[i].next) {
            ll v = edge[i].to;
            if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost) {
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i;
                if(!vis[v]) {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    if(pre[t] == -1) return 0;
    else return 1;
}
 
ll MCMF(ll s, ll t) {
    minCost = 0;
    maxFlow = 0;
    while(spfa(s, t)) {
        ll minn = inf;
        for(ll i = pre[t]; i != -1; i = pre[edge[i ^ 1].to]) {
            if(minn > edge[i].cap - edge[i].flow)
                minn = edge[i].cap - edge[i].flow;
        }
        for(ll i = pre[t]; i != -1; i = pre[edge[i ^ 1].to]) {
            edge[i].flow += minn;
            edge[i ^ 1].flow -= minn;
            minCost += edge[i].cost * minn;
        }
        maxFlow += minn;
    }
    return maxFlow;
}
 
int main() {
    init();
    ll p, a, b, c, d;
    scanf("%lld", &n);
    s = 0, t = 2 * n + 1;
    for(ll i = 1; i <= n; ++i) {///1~n晚上 n + 1~2 * n早上 s = 0 t = 2 * n + 1
        scanf("%lld", &ned[i]);
        addedge(s, i, ned[i], 0);   ///每天晚上接受超级源点（每天早上）的脏餐巾
        addedge(i + n, t, ned[i], 0);///每天早上需要干净的餐巾 连超级汇点
    }
    scanf("%lld%lld%lld%lld%lld", &p, &a, &b, &c, &d);
    for(int i = 2; i <= n; ++i) {
        addedge(i - 1, i, inf, 0);  ///前一天晚上的脏餐巾可以向后一天转移
        int tmp = i - 1 + a;
        if(tmp <= n)
            addedge(i - 1, tmp + n, inf, b);    ///脏餐巾慢洗 第i + b天后可以用
        tmp = i - 1 + c;
        if(tmp <= n)
            addedge(i - 1, tmp + n, inf, d);    ///脏餐巾快洗 第i + d天后可以用
    }
    for(int i = 1; i <= n; ++i)
        addedge(s, i + n, inf, p);  ///每天早上都可以购买新餐巾
    MCMF(s, t);
    printf("%lld\n", minCost);
	return 0;
}