有一个人,进行\(n\)个小时的活动。
每个活动要么是睡觉(\(s\)),要么是打隔膜(\(e\))。
规定任意一段连续的\(k\)个小时,至少\(t_1\)小时是睡觉,至少\(t_2\)小时是打隔膜。
对于第\(i\)个小时,睡觉的收益是\(s_i\),打隔膜的收益是\(e_i\),问最大收益。
$ 1 \leq k \leq n \leq 10^3 $
我们假设初始每一个小时全都是睡觉,收益为\(\sum_{i=1}^{n}s_i\)。
之后我们就是选一些小时变成打隔膜,每选一个,单个收益是\(e_i - s_i\)。
我们设\(x_i\)表示第i个小时要不要变成打隔膜。
我们设\(sum_i=\sum_{j=i}^{k+i-1}x_j\),那么有如下方程:
整理整理,我们再引入两种变量,将不等式变成等式:
我们对式子做差分,并且将所有变量的符号都变成正号,可以得到:
然后我们就发现这个式子非常优美,于是我们就可以建图了。
而且因为我们每一个\(x_i\)是带费用的,所以要建费用流的图。
这是老套路了,因为每一个变量都是等号左右各出现一次。
所以我们可以将每一个等号看成一个点,每一个变量看成一条边,
对于每一个等式,我们将等号左侧看作流入,右侧看作流出,
对于每一条边,容量就是这个变量的上下界了(当然,就像这道题,下界一般为\(0\))。
对于常数项,如果是流入,就从\(S\)连入,否则就连向\(T\),容量是常数项的值。
特殊的,对于这道题,因为每一个\(x\)变量是有费用的,
所以我们对于\(x_i\)的边,要赋一个\(e_i-s_i\)的费用。
之后就是最大费用最大流的事了。
#include <bits/stdc++.h>
using namespace std;
int read() {
int res = 0;
char c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) res = res * 10 + c - ‘0‘, c = getchar();
return res;
}
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
namespace Max_flow {
const int maxn = 1e4 + 4;
const int inf_1 = 0x3f3f3f3f;
const ll inf_2 = 0x3f3f3f3f3f3f3f3f;
queue<int> que;
int S, T, e_cnt, head[maxn], pre[maxn][2];
int nxt[maxn], to[maxn], flow[maxn], vis[maxn];
ll cost[maxn], dis[maxn];
void init(int _S, int _T) {
S = _S, T = _T, e_cnt = -1;
for (int i = S; i <= T; i++) head[i] = -1;
}
void Add(int u, int v, int _flow, ll _cost) {
// cerr << "Add(" << u << ", " << v << ", " << _flow << ", " << _cost << ")\n";
nxt[++e_cnt] = head[u], head[u] = e_cnt, to[e_cnt] = v;
flow[e_cnt] = _flow, cost[e_cnt] = _cost;
nxt[++e_cnt] = head[v], head[v] = e_cnt, to[e_cnt] = u;
flow[e_cnt] = 0, cost[e_cnt] = -_cost;
}
bool bfs() {
while (!que.empty()) que.pop();
for (int i = S; i <= T; i++) pre[i][0] = pre[i][1] = 0;
for (int i = S; i <= T; i++) vis[i] = 0;
for (int i = S; i <= T; i++) dis[i] = inf_2;
dis[S] = 0, que.push(S), vis[S] = 1;
while (!que.empty()) {
int now = que.front();
vis[now] = 0, que.pop();
for (int i = head[now]; ~i; i = nxt[i]) {
if (flow[i] > 0 && dis[to[i]] > dis[now] + cost[i]) {
dis[to[i]] = dis[now] + cost[i];
pre[to[i]][0] = now, pre[to[i]][1] = i;
if (!vis[to[i]]) que.push(to[i]), vis[to[i]] = 1;
}
}
}
return dis[T] != inf_2;
}
ll Min_cost() {
ll res = 0;
while (bfs()) {
int New_flow = 0x3f3f3f3f;
for (int i = T; i != S; i = pre[i][0])
New_flow = min(New_flow, flow[pre[i][1]]);
res += dis[T] * New_flow;
for (int i = T; i != S; i = pre[i][0]) flow[pre[i][1]] -= New_flow;
for (int i = T; i != S; i = pre[i][0]) flow[pre[i][1] ^ 1] += New_flow;
}
return res;
}
} // namespace Max_flow
using Max_flow::Add;
const int maxn = 1e3 + 3;
int N, K, t_1, t_2, _s[maxn], _e[maxn], id[maxn];
ll Hahawang_answer = 0;
int main() {
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
N = read(), K = read(), t_1 = read(), t_2 = 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++) Hahawang_answer += _s[i];
Max_flow::init(0, (N - K + 1) * 2 + 2);
const int inf = 0x3f3f3f3f, dot_num = (N - K + 1) << 1 | 1;
for (int i = 1; i <= N - K + 1; i++) Add(i << 1 | 1, i << 1, inf, 0);
for (int i = 1; i <= N - K + 1; i++) Add((i - 1) << 1 | 1, i << 1, inf, 0);
for (int i = 1; i <= K; i++) {
id[i] = Max_flow::e_cnt + 1;
Add(min(i << 1 | 1, dot_num), 1, 1, -(_e[i] - _s[i]));
}
for (int i = 1; i <= N - K; i++) {
id[K + i] = Max_flow::e_cnt + 1;
Add(min((i + K) << 1 | 1, dot_num), i << 1 | 1, 1, -(_e[K + i] - _s[K + i]));
}
for (int i = 1; i <= N - K + 1; i++) Add(i << 1, Max_flow::T, K - t_1 - t_2, 0);
for (int i = 1; i <= N - K; i++) Add(Max_flow::S, i << 1 | 1, K - t_1 - t_2, 0);
Add(1, Max_flow::T, t_2, 0), Add(Max_flow::S, dot_num, K - t_1, 0);
printf("%lld\n", Hahawang_answer - Max_flow::Min_cost());
for (int i = 1; i <= N; i++) putchar(Max_flow::flow[id[i]] ? ‘S‘ : ‘E‘);
putchar(‘\n‘);
return 0;
}
https://www.cnblogs.com/CQzhangyu/p/7894559.html
原文:https://www.cnblogs.com/tacmon52818/p/12712982.html