你养了一只猫,为了让它快乐地成长,你需要合理地安排它每天的作息时间。假设一天分为nn个时刻,猫在每个时刻要么是吃东西,要么是睡觉。在第ii个时刻,假如猫是去吃东西,那么它能获得愉悦值eie_i,假如是去睡觉,那么能获得的愉悦值为sis_i

猫要成长,不仅仅需要快乐,还需要健康的作息。经过研究,对于每一个连续的长度为kk的作息区间,即所有的时刻区间[i,i+k1],1ink+1[i, i + k - 1], 1 \le i \le n - k + 1,猫都要至少有t1t1的时刻用来睡觉,t2t2的时刻用来吃东西,这样猫才能健康成长。

现在你想合理地安排一天中的这nn个时刻,使得猫在能健康成长的前提下,获得尽量多的愉悦值。

kn1000k \le n \le 1000

LOJ 6079

Solution

限制条件是区间,考虑费用流解决线性规划问题

先假设每天都吃东西,然后令xix_i表示第ii填是否睡觉,若睡觉则产生sieis_i - e_i的愉悦值。然后考虑限制,可以列出kk个不等式

{t1x1+x2++xkkt2t1x2+x3++xk+1kt2t1xnk+1+xnk+2++xnkt2 \begin{cases} t_1\leq x_1+x_2+\cdots+x_k\leq k-t_2\\ t_1\leq x_2+x_3+\cdots+x_{k+1}\leq k-t_2\\ \quad\quad\quad\quad\quad\quad\quad\quad\vdots\\ t_1\leq x_{n-k+1}+x_{n-k+2}+\cdots+x_n\leq k-t_2 \end{cases}

添加辅助变量yi,ziy_i, z_i,将不等式转化为等式

{ x1+x2++xk=t1+y1x1+x2++xk=kt2z1x2+x3++xk+1=t1+y2 \begin{cases}\ x_1+x_2+\cdots+x_k&=t_1+y_1\\ x_1+x_2+\cdots+x_k&=k-t_2-z_1\\ x_2+x_3+\cdots+x_{k+1}&=t_1+y_2\\ &\vdots \end{cases}

在末尾添加方程0=00 = 0,然后差分

{ x1+x2++xk=t1+y1y1+z1=kt1t2xk+1+kt1t2=x1+y2+z1kt2znk+1=xnk+1+xnk+2++xn \begin{cases}\ x_1+x_2+\cdots+x_k&=t_1+y_1\\ y_1+z_1&=k-t_1-t_2\\ x_{k+1}+k-t_1-t_2&=x_1+y_2+z_1\\ &\vdots\\ k-t_2-z_{n-k+1}&=x_{n-k+1}+x_{n-k+2}+\cdots+x_n \end{cases}

由于每个变量要求非负,且恰好在等号左右两边各出现一次,于是把每个等式看成一个点,变量看成边,变量的取值即为流量,则一个方程即表示这个点的流量平衡。假设等号左边流出,右边流入

对于初始变量(xix_i),从左边所在的方程连向右边的方程,连(1,siei)(1, s_i - e_i)

对于添加的变量(yi,ziy_i, z_i),同上,连(,0)(\infty, 0)

对于常数项(t1,kt1t2,kt2t_1, k - t_1 - t_2, k - t_2),若在左边,则从方程连向汇点;反之从源点连向方程,容量为它的值,费用为00

最大费用最大流的答案加上i=1nei\sum_{i=1}^{n} e_i就是答案

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch - '0');
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 1e3;

int N, K, t1, t2;
int A[MAXN + 5], B[MAXN + 5];

namespace FLOW
{
const int MAXN = :: MAXN * 2;
const int MAXM = 4e6;

int e, Begin[MAXN + 5], To[MAXM + 5], Next[MAXM + 5];
LL W[MAXM + 5], Cost[MAXM + 5];
int Cur[MAXN + 5], Mark[MAXN + 5];
int S = 0, T = MAXN + 1;

inline void add_edge (int x, int y, LL z, LL c) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; W[e] = z; Cost[e] = c; }

inline void add (int x, int y, LL z, LL c, int id = 0)
{
if (id) Mark[id] = e + 1;
add_edge (x, y, z, c), add_edge (y, x, 0, -c);
}

LL dis[MAXN + 5];
int vis[MAXN + 5];
LL flow, cost;

inline int spfa ()
{
for (int i = S; i <= T; ++i) dis[i] = LLONG_MAX, vis[i] = 0;
dis[S] = 0;

static queue <int> Q; Q.push (S);

while (!Q.empty())
{
int x = Q.front(); Q.pop();
vis[x] = 0;

for (int i = Begin[x]; i; i = Next[i])
{
int y = To[i];
if (W[i] > 0 && Chkmin (dis[y], dis[x] + Cost[i]) && !vis[y])
Q.push (y), vis[y] = 1;
}
}

return dis[T] != LLONG_MAX;
}

inline LL dfs (int x, LL k)
{
vis[x] = 1;
if (x == T || !k) return k;

LL sum = 0;
for (int &i = Cur[x]; i; i = Next[i])
{
int y = To[i]; LL tmp;
if (!vis[y] && dis[y] == dis[x] + Cost[i] && W[i] > 0 && (tmp = dfs (y, min (k, W[i]))))
{
cost += tmp * Cost[i];
W[i] -= tmp, W[i ^ 1] += tmp;
k -= tmp, sum += tmp;
if (!k) return sum;
}
}
return sum;
}

inline void work ()
{
while (spfa ())
{
for (int i = S; i <= T; ++i) Cur[i] = Begin[i], vis[i] = 0;

flow += dfs (S, LLONG_MAX);
}
}

inline void print ()
{
for (int i = 1; i <= N; ++i)
{
int x = Mark[i];
if (W[x] == 1) printf("E");
else printf("S");
}
}

inline void init ()
{
flow = cost = 0;
e = 1;
memset (Begin, 0, sizeof Begin);
}
}

using FLOW :: S;
using FLOW :: T;

inline void Solve ()
{
FLOW :: init ();

int lim = 2 * (N - K + 1) + 1;

for (int i = 1; i <= N; ++i)
{
int x = 2 * (i - K) + 1, y = 2 * i + 1;
if (i <= K) x = 1;
if (i >= N - K + 1) y = lim;
FLOW :: add (x, y, 1, -(A[i] - B[i]), i);
}

for (int i = 1; i <= N - K + 1; ++i)
{
FLOW :: add (2 * i, 2 * i - 1, INT_MAX, 0);
FLOW :: add (2 * i, 2 * i + 1, INT_MAX, 0);
}

FLOW :: add (S, 1, t1, 0), FLOW :: add (lim, T, K - t2, 0);
for (int i = 3; i < lim; i += 2) FLOW :: add (i, T, K - t1 - t2, 0);
for (int i = 2; i < lim; i += 2) FLOW :: add (S, i, K - t1 - t2, 0);

FLOW :: work ();

LL ans = -FLOW :: cost;
for (int i = 1; i <= N; ++i) ans += B[i];

cout << ans << endl;
FLOW :: print ();
}

inline void Input ()
{
N = read<int>(), K = read<int>(), t1 = read<int>(), t2 = read<int>();
for (int i = 1; i <= N; ++i) A[i] = read<int>();
for (int i = 1; i <= N; ++i) B[i] = read<int>();
}

int main ()
{

#ifdef hk_cnyali
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif

Input ();
Solve ();

return 0;
}