Chlience

【题解】LOJ 6079 「2017 山东一轮集训 Day7」养猫
Problem每个时刻可以选择睡觉或者吃东西,分别获得 $s_i$ 和 $e_i$ 的权值并且要求在连续的长度 $...
扫描右侧二维码阅读全文
11
2019/03

【题解】LOJ 6079 「2017 山东一轮集训 Day7」养猫

Problem

每个时刻可以选择睡觉或者吃东西,分别获得 $s_i$ 和 $e_i$ 的权值
并且要求在连续的长度 $k$ 的时间内至少有 $ms$ 的时间用来睡觉, $me$ 的时间用来吃东西,求最大权值

BZOJ 4842 [Neerc2016]Delight for a Cat 双倍经验

Thought

费用流经典约束模型

先假设所有时间用来睡觉,那么只需要考虑将某些时刻变为吃东西即可
开始时 $ans=\sum_{i=1}^n s_i$

设 $x_i$ 为 $i$ 时刻是否吃东西,那么最终答案为 $ans+\sum_{i=1}^{n}x_i(e_i-s_i)$
根据限制条件可得:

$$ sum[n]=\sum_{i=n-k+1}^{n}x_i\\ me\leq sum[n]\leq k-ms $$

易得 $sum[n+1]-sum[n]=x_{n+1}-x_{n-k+1}$

如果需要去除最小限制,只需要令 $sum'[n]=sum[n]-me$ ,则只需要保证 $sum'[n]\leq k-ms-me$

具体实现方法只需要在原来的 $sum[k]=\sum_{i=1}^{k}x_k$ 处,令 $sum'[k]=\sum_{i=1}^{k}x_k-me$ ,由于后面的 $sum$ 都是由差分得到,自然就变为了 $sum'$

然而这个方法会导致某些边往回走,导致负环等情况,比较麻烦,所以说我选择了另外一种方法

设点 $i$ 表示 $[i,i+k-1]$ 中选了多少点,限制仍然是每个区间只能取 $[me,k-ms]$ 个
发现选择某个点 $i$ 会影响包含它的区间 $[i,i+k-1]$ ,相当于做了一次区间覆盖

需要保证每个点被覆盖 $[me,k-ms]$ 次,即有上下界的区间覆盖问题

思考没有下界的区间问题如何解决
发现加上下界只需要让经过没有 $(i,i+1)$ 的边的流量大于等于下界即可,即限制 $(i,i+1)$ 的流量最大为 $k-ms-me$ ,由于一共要通过 $k-ms$ 的流量,那么至少 $me$ 的流量要通过福覆盖边,这样即能算出答案

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 1010;
const ll MAX = 4557430888798830399ll;
struct Edge {
    int t, n, f;
    ll d;
}e[N << 3];
int head[N], Etot = 1;

int n, k, ms, me;
int S[N], E[N];
int id[N];
ll ans;
int s, t, ss;

ll dis[N];
bool vis[N];
queue <int> q;

int nodeCnt;
int f[N], d[N], cur[N];

void addedge(int u, int v, int f, int d) {
    e[++ Etot] = {v, head[u], f, d};
    head[u] = Etot;
    e[++ Etot] = {u, head[v], 0, - d};
    head[v] = Etot;
}

bool SPFA() {
    memset(dis, 0x3f3f3f3f, sizeof(dis));
    dis[t] = 0; vis[t] = 1;
    q.push(t);
    while(!q.empty()) {
        int x = q.front(); q.pop(); vis[x] = 0;
        for(int i = head[x]; i; i = e[i].n) {
            if(e[i ^ 1].f > 0 && dis[x] + e[i ^ 1].d < dis[e[i].t]) {
                dis[e[i].t] = dis[x] + e[i ^ 1].d;
                if(!vis[e[i].t])
                    q.push(e[i].t);
                vis[e[i].t] = 1;
            }
        }
    }
    if(dis[s] == MAX) return false;
    return true;
}

int dfs(int x, int flow) {
    if(x == t) return flow;
    int use = 0;
    for(int i = cur[x]; i; i = e[i].n) {
        cur[x] = i;
        if(dis[x] - e[i].d != dis[e[i].t]) continue;
        if(d[e[i].t] + 1 != d[x] || !e[i].f) continue;
        int tmp = dfs(e[i].t, min(e[i].f, flow - use));
        e[i].f -= tmp;
        e[i ^ 1].f += tmp;
        use += tmp;
        if(use == flow) return use;
    }
    cur[x] = head[x];
    if(!(-- f[d[x]]))
        d[s] = nodeCnt;
    ++ f[++ d[x]];
    return use;
}

void MCMF() {
    while(SPFA()) {
        memset(f, 0, sizeof(f));
        memset(d, 0, sizeof(d));
        memset(cur, 0, sizeof(cur));
        f[0] = nodeCnt;
        ll flow = 0;
        while(d[s] < nodeCnt)
            flow += dfs(s, 1 << 30);
        ans -= flow * dis[s];
    }
    printf("%lld\n", ans);
}

int main() {
    n = read(); k = read(); ms = read(); me = read();
    for(int i = 1; i <= n; ++ i)
        S[i] = read();
    for(int i = 1; i <= n; ++ i)
        E[i] = read();
    for(int i = 1; i <= n; ++ i)
        ans += S[i];
    s = n + 1; t = n + 2; ss = n + 3;
    addedge(s, ss, k - ms, 0);
    for(int i = 1; i <= k; ++ i)
        addedge(ss, i, 1 << 28, 0);
    for(int i = 1; i <= n; ++ i) {
        if(i + 1 <= n)
            addedge(i, i + 1, k - ms - me, 0);
        else
            addedge(i, t, k - ms - me, 0);
        id[i] = Etot + 1;
        if(i + k <= n)
            addedge(i, i + k, 1, S[i] - E[i]);
        else
            addedge(i, t, 1, S[i] - E[i]);
    }
    nodeCnt = n + 3;
    MCMF();
    for(int i = 1; i <= n; ++ i)
        if(e[id[i]].f)
            putchar('S');
        else
            putchar('E');
    return 0;
}
Last modification:March 11th, 2019 at 07:50 pm

Leave a Comment