bzoj 4842 [Neerc2016]Delight for a Cat

Description

ls是一个特别堕落的小朋友，对于n个连续的小时，他将要么睡觉要么打隔膜，一个小时内他不能既睡觉也打隔膜，因此一个小时内他只能选择睡觉或者打隔膜，当然他也必须选择睡觉或打隔膜，对于每一个小时，他选择睡觉或打隔膜的愉悦值是不同的，对于第i个小时，睡觉的愉悦值为si，打隔膜的愉悦值为ei，同时又有一个奥妙重重的规定：对于任意一段连续的k小时，ls必须至少有t1时间在睡觉，t2时间在打隔膜。那么ls想让他获得的愉悦值尽量大，他该如何选择呢？

Input

第一行四个整数,n,k(1<=k<=n<=1000),t1,t2(0<=t1,t2<=k;t1+t2<=k),含义如上所述。
接下来一行n个整数，第i个整数si(0<=si<=1e9)表示睡觉的愉悦值。
接下来一行n个整数，第i个整数ei(0<=ei<=1e9)表示打隔膜的愉悦值。

Output

第一行输出最大的愉悦值。
接下来一行输出一个长度为n的字符串
第i个字符为E则代表第i小时在打隔膜，第i个字符为S则代表第i个小时在睡觉。

Sample Input

10 4 1 2

1 2 3 4 5 6 7 8 9 10

10 9 8 7 6 5 4 3 2 1

Sample Output

69

EEESESEESS

题解

我们先让所有时间都睡觉。。假设有一天吃饭，那么我们换成吃饭的费用就是$e_i – s_i$

如果只有睡觉的限制，那么我们要满足的就是从$i$连到$i+1$的，容量不能超过$t_1$，在$i$连到$i+1$的边都表示这天睡觉，容量$t_1$，费用0。

如果吃饭没有限制，就可以从每个$i$连到$i+K$（不够的话到汇点），容量为1，费用为$e_i−s_i$。

然后求最大费用最大流就好了。

考虑有了吃饭限制，相当于我从$i$到$i+1$的边容量变为$r−l$（上界-下界），就代表我一定要有吃饭的流量。

从$i$到$i+1$画一条纵截线，与其相交并且是$i$到$i+k$这样的边至少有$l$个。

再对源点容量做一下限制即可。

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define M 200100
#define N 100100
#define inf 1e17
#define min(x,y) ((x<y)?(x):(y))
using namespace std;
typedef pair<long long, long long> Pair;
struct MFMC {
    struct node {
        int from, to, next;
        long long cost, flow;
    }e[M];
    int tot, st[N];
    int pe[N], pv[N], vis[N];
    long long dis[N];
    void init() {
        tot = -1, memset(e, -1, sizeof e);
        memset(st, -1, sizeof st);
    }
    void add(int x, int y, long long z, long long zz) {
        e[++tot].to = y, e[tot].from = x;
        e[tot].flow = z, e[tot].cost = zz;
        e[tot].next = st[x], st[x] = tot;
    }
    void add_edge(int x, int y, long long z, long long zz) {
        add(x, y, z, zz), add(y, x, 0, -zz);
    }
    queue <int> que;
    bool spfa(int S, int T) {
//      memset(dis, 0x33, sizeof dis);
        for (int i = 0; i <= T; ++i)
            dis[i] = inf;
        memset(vis, 0, sizeof vis);
        que.push(S), vis[S] = 1, dis[S] = 0;
        while(!que.empty()) {
            int now = que.front();
            que.pop();
            vis[now] = 0;
            for (int i = st[now]; ~i; i = e[i].next)
                if (e[i].flow > 0 && dis[e[i].to] > dis[now] + e[i].cost) {
                    dis[e[i].to] = dis[now] + e[i].cost;
                    pe[e[i].to] = i, pv[e[i].to] = now;
                    if (!vis[e[i].to])
                        vis[e[i].to] = 1, que.push(e[i].to);
                }
        }
        return dis[T] < inf;
    }
    Pair mfmc(int S, int T) {
        long long COST = 0, FLOW = 0, flow;
        while(spfa(S, T)) {
            flow = inf;
            for (int i = T; i != S; i = pv[i])
                flow = min(flow, e[pe[i]].flow);
            COST += flow * dis[T];
            FLOW += flow;
            for (int i = T; i != S; i = pv[i])
                e[pe[i]].flow -= flow, e[pe[i] ^ 1].flow += flow;
        }
        return make_pair(FLOW, COST);
    }
}mcmf;
int n, m, k, x, y, z, t1, t2, a[N], b[N];
int main() {
    mcmf.init();
    scanf("%d%d%d%d", &n, &k, &t1, &t2);
    long long sum = 0;
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]), sum += a[i];
    for (int i = 1; i <= n; ++i)
        scanf("%d", &b[i]);
    int mins = t2, maxs = k - t1, s = n + 1, S = s + 1, T = S + 1;
    for (int i = 1; i <= n; ++i)
        mcmf.add_edge(i, i + k > n ? T : i + k, 1, -(b[i] - a[i]));
    for (int i = 1; i <= n; ++i)
        mcmf.add_edge(i, i + 1 > n ? T : i + 1, maxs - mins, 0);
    for (int i = 1; i <= k; ++i)
        mcmf.add_edge(s, i, inf, 0);
    mcmf.add_edge(S, s, maxs, 0);
    Pair ans = mcmf.mfmc(S, T);
    printf("%lld\n", sum - ans.second);
    for (int i = 1; i <= 2 * n - 1; i += 2)
        if (mcmf.e[i].flow)
            putchar('E');
        else
            putchar('S');
}