Description：

有 $n$ 个小时要么 $A$ 要么 $B$ ， $A$ 或 $B$ 的价值是不同的，对于第 $i$ 个小时， $A$ 的价值为 $s_i$ ， $B$ 的价值为 $e_i$ ，对于连续的 $k$ 小时，必须至少有 $t1$ 时间 $A$ ， $t2$ 时间 $B$ 。最大化价值。

$1\le n \le 1000$

Solution：

首先是先加上所有 $s_i$ ，然后把每个点的价值变成 $e_i-s_i$ ，这样就变成了每个区间内至多选 $k-t1$ 个，至少选 $t2$ 个。

看上去是个有上下界的费用流，但是这题可以有一些别的方法保证它满足下界，具体做法是像志愿者招募那题一样，设第 $i$ 个点表示区间 $[i-k+1,i]$ ，那么如果选了 $p$ ，区间 $[p-k+1,p]$ 到 $[p,p+k-1]$ 都被加了一，这就转化成了一个区间覆盖的形式，即如果选了点 $i$ ，会把区间 $[p,p+k-1]$ 都加一。

从源向 $[1,k]$ 中的点连容量 $INF$ 费用为 $0$ 的边，从每个点向下一个点连容量 $maxflow-minflow$ 费用为 $0$ 的边，代表这些流是可以流也可以不流的，再另建一个超级源，超级源向源点连容量 $maxflow$ 费用为 $0$ 的边限制最高流量，这样我们只要保证满流，那 $minflow$ 的流量是一定会被流过的，然后每个点向它后面的第 $k$ 个点连容量为一费用为 $-(e_i-s_i)$ 的边，这样满流是一定能保证的，而这样也能代表这个区间被花了 $-(e_i-s_i)$ 的价值覆盖，如果从最小割的角度理解，会发现每个断面都有 $maxflow$ 的流量，注意末尾连边的特殊处理。

方案也很好求，只要判断代表覆盖的边是不是满流即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int n,k,t1,t2;

#define MAXN 2010

int val1[MAXN],val2[MAXN];

int val[MAXN];

typedef long long ll;

int s,t,ss;

#define INF 0x3f3f3f3f

struct edge

{

	int to,nxt,c,f;

}e[MAXN * 4 * 2];

int edgenum = 0;

int lin[MAXN];

inline void add(int a,int b,int f,int c)

{

	e[edgenum].to = b;e[edgenum].c =  c;e[edgenum].f = f;e[edgenum].nxt = lin[a];lin[a] = edgenum;++edgenum;

	e[edgenum].to = a;e[edgenum].c = -c;e[edgenum].f = 0;e[edgenum].nxt = lin[b];lin[b] = edgenum;++edgenum;

	return;

}

ll d[MAXN];

int pre[MAXN],rate[MAXN];

bool v[MAXN];

ll sum;

bool SPFA()

{

	memset(d,0x3f,sizeof(d));

	memset(pre,0,sizeof(pre));

	memset(rate,0,sizeof(rate));

	memset(v,false,sizeof(v));

	queue<int> q;

	d[s] = 0;q.push(s);v[s] = true;

	rate[s] = INF;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		v[k] = false;

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].c && e[i].f)

			{

				d[e[i].to] = d[k] + e[i].c;

				pre[e[i].to] = i;

				rate[e[i].to] = min(rate[k],e[i].f);

				if(!v[e[i].to])

				{

					v[e[i].to] = true;

					q.push(e[i].to);

				}

			}

		}

	}

	return (d[t] != 0x3f3f3f3f3f3f3f3f);

}

ll flow()

{

	for(int i = t;i != s;i = e[pre[i] ^ 1].to)

	{

		e[pre[i]].f -= rate[t];

		e[pre[i] ^ 1].f += rate[t];

	}

	return rate[t] * d[t];

}

ll EK()

{

	ll ans = 0;

	while(SPFA())ans += flow();

	return ans;

}

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d%d%d%d",&n,&k,&t1,&t2);

	sum = 0;

	for(register int i = 1;i <= n;++i)val1[i] = read();

	for(register int i = 1;i <= n;++i)val2[i] = read();

	for(register int i = 1;i <= n;++i)sum += val1[i];

	for(register int i = 1;i <= n;++i)val[i] = val2[i] - val1[i];

	register int maxflow = k - t1,minflow = t2;

	t = n + 1,s = t + 1,ss = s + 1;

	for(register int i = 1;i <= k;++i)add(ss,i,INF,0);

	for(register int i = 1;i <= n;++i)add(i,i + 1,maxflow - minflow,0);

	int top = edgenum;

	for(register int i = 1;i <= n - k;++i)add(i,i + k,1,-val[i]);

	for(register int i = n - k + 1;i <= n;++i)add(i,t,1,-val[i]);

	add(s,ss,maxflow,0);

	cout << sum - EK() << endl;

	for(register int p = 1;p <= n - k;++p)

	{

		register bool found = false;

		for(register int i = lin[p];i != -1;i = e[i].nxt)

			if(e[i].to == p + k && i >= top && e[i].f == 0)

				found = true;

		if(found)putchar('E');

		else putchar('S');

	}

	for(register int p = n - k + 1;p <= n;++p)

	{

		register bool found = false;

		for(register int i = lin[p];i != -1;i = e[i].nxt)

			if(e[i].to == n + 1 && i >= top && e[i].f == 0)

				found = true;

		if(found)putchar('E');

		else putchar('S');

	}

	puts("");

	return 0;

}