Luogu

Gym

分析

考虑线性规划。设 $x_i$ 为第 $i$ 小时是否吃饭，可以列出线性规划
$$
\begin{matrix}
\mathrm{maximize } \sum_{i=1}^n x_i(e_i-s_i)+\sum_{i=1}^n s_i\\
\mathrm{s.t. }\begin{cases}x_1+x_2+\cdots+x_k\geq m_e\\x_1+x_2+\cdots+x_k\leq k-m_s\\\cdots\\x_{n-k+1}+x_{n-k+2}+\cdots+x_n\geq m_e\\x_{n-k+1}+x_{n-k+2}+\cdots+x_n\leq k-m_s\\0\leq x_1,x_2,\cdots,x_n\leq 1\end{cases}
\end{matrix}
$$
发现是全幺模矩阵，所以一定有整数解，可以考虑费用流。

按照惯例添加辅助变量
$$
\begin{cases}x_1+x_2+\cdots+x_k-y_1=m_e\\x_1+x_2+\cdots+x_k+z_1=k-m_s\\\cdots\\x_{n-k+1}+x_{n-k+2}+\cdots+x_n-y_{n-k+1}=m_e\\x_{n-k+1}+x_{n-k+2}+\cdots+x_n+z_{n-k+1}=k-m_s\end{cases}
$$
然后差分一下
$$
\begin{cases}x_1+x_2+\cdots+x_k-y_1=m_e\\z_1+y_1=k-m_s-m_e\\\cdots\\z_{n-k+1}+y_{n-k+1}=k-m_s-m_e\\-x_{n-k+1}-x_{n-k+2}-\cdots-x_n-z_{n-k+1}=m_s-k\end{cases}
$$
用 NOI2008 志愿者招募 一题的方法建图求最大费用最大流即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000+10;
const int V=2001+10,E=6000+10;
const int inf=0x3f3f3f3f;

int n,k,m,ms,me,a[N],b[N],id[N];

struct edge { int v,w,c,nxt; } e[E<<1];
int head[V],ecnt=1;
void addEdge(int u,int v,int w,int c) {
    e[++ecnt]=(edge){v,w,c,head[u]},head[u]=ecnt;
    e[++ecnt]=(edge){u,0,-c,head[v]},head[v]=ecnt;
}

int S,T,inq[V],pre[V]; ll dis[V];
bool spfa() {
    memset(dis,0xc0,sizeof(dis)),memset(pre,0,sizeof(pre));
    queue<int> Q; Q.push(S),dis[S]=0;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(),inq[u]=0;
        for (int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w,c=e[i].c;
            if (w&&dis[u]+c>dis[v]) {
                dis[v]=dis[u]+c,pre[v]=i;
                if (!inq[v]) Q.push(v),inq[v]=1;
            }
        }
    }
    return pre[T]!=0;
}

int main() {
    n=read(),k=read(),m=(n-k+1)<<1,ms=read(),me=read(); ll sum=0;
    for (int i=1;i<=n;++i) a[i]=read();
    for (int i=1;i<=n;++i) b[i]=read();
    for (int i=1;i<=n;++i) sum+=a[i],b[i]-=a[i];
    S=0,T=m+2;
    for (int i=1;i<=m+1;++i) {
        if (i==1) addEdge(S,i,me,0);
        else if (i==m+1) addEdge(i,T,k-ms,0);
        else {
            int w=(i&1)?me+ms-k:k-me-ms;
            if (w>0) addEdge(S,i,w,0);
            else addEdge(i,T,-w,0);
        }
    }
    for (int i=1;i<=n;++i) {
        int l=max(0,i-k)<<1|1,r=min(i,n-k+1)<<1|1;
        addEdge(l,r,1,b[i]),id[i]=ecnt^1;
    }
    for (int i=2;i<=m;i+=2) addEdge(i,i-1,inf,0),addEdge(i,i+1,inf,0);
    ll maxcost=0;
    while (spfa()) {
        int f=inf;
        for (int i=pre[T];i;i=pre[e[i^1].v]) f=min(f,e[i].w);
        for (int i=pre[T];i;i=pre[e[i^1].v]) e[i].w-=f,e[i^1].w+=f;
        maxcost+=dis[T]*f;
    }
    printf("%lld\n",sum+maxcost);
    for (int i=1;i<=n;++i) putchar(e[id[i]].w?'S':'E');
    return 0;
}