4842: [Neerc2016]Delight for a Cat
Time Limit: 10 Sec Memory Limit: 128 MBSec Special JudgeSubmit: 384 Solved: 123
[Submit][Status][Discuss]
Description
ls是一个特别堕落的小朋友，对于n个连续的小时，他将要么睡觉要么打隔膜，一个小时内他不能既睡觉也打隔膜
，因此一个小时内他只能选择睡觉或者打隔膜，当然他也必须选择睡觉或打隔膜，对于每一个小时，他选择睡觉或
打隔膜的愉悦值是不同的，对于第i个小时，睡觉的愉悦值为si，打隔膜的愉悦值为ei，同时又有一个奥妙重重的
规定：对于任意一段连续的k小时，ls必须至少有t1时间在睡觉，t2时间在打隔膜。那么ls想让他获得的愉悦值尽
量大，他该如何选择呢？
Input
第一行四个整数,n,k(1<=k<=n<=1000),t1,t2(0<=t1,t2<=k;t1+t2<=k),含义如上所述。
接下来一行n个整数，第i个整数si(0<=si<=1e9)表示睡觉的愉悦值。
接下来一行n个整数，第i个整数ei(0<=ei<=1e9)表示打隔膜的愉悦值。
Output
第一行输出最大的愉悦值。
接下来一行输出一个长度为n的字符串
第i个字符为E则代表第i小时在打隔膜，第i个字符为S则代表第i个小时在睡觉。
Sample Input
10 4 1 2
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
Sample Output
69
EEESESEESS
EEESESEESS
HINT
Source
这个题和序列那道题很像
首先我们强制每一个点都在打隔膜
那么问题就变成了 对于任意一段k时间 睡觉时间不能小于t1，不能大于k-t2
不能大于k-t2可以像序列那道题一样进行建图，可是我们还要对不能小于t1进行限制
那么就对于所有i连向i+1的边，流量变为k-t1-t2即可，不难发现这样建图可以满足所有限制。
/**************************************************************
Problem: 4842
User: zhangenming
Language: C++
Result: Accepted
Time:5136 ms
Memory:55984 kb
****************************************************************/
#include <bits/stdc++.h>
#define eps 1e-7
#define ll long long
using namespace std;
inline int read(){
int x=0;int f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int MAXN=1e6+10;
const ll inf=(ll)1e15;
struct node{
int y,next,back;
ll w,flow;
}e[MAXN];
int linkk[MAXN],len,vis[MAXN],s,t,n,k,num[MAXN],a[MAXN],b[MAXN],t1,t2;
ll ans,dis[MAXN];
inline void insert(int x,int y,ll f,ll c){
e[++len].y=y;e[len].next=linkk[x];linkk[x]=len;e[len].flow=f;e[len].back=len+1;e[len].w=c;
e[++len].y=x;e[len].next=linkk[y];linkk[y]=len;e[len].flow=0;e[len].back=len-1;e[len].w=-c;
}
inline bool spfa(){
deque<int>q;
for(int i=s;i<=t;i++) vis[i]=0,dis[i]=-inf;
dis[t]=0;vis[t]=1;
q.push_back(t);
while(!q.empty()){
int tn=q.front();q.pop_front();
for(int i=linkk[tn];i;i=e[i].next){
if(e[e[i].back].flow&&dis[e[i].y]<dis[tn]-e[i].w){
dis[e[i].y]=dis[tn]-e[i].w;
if(!vis[e[i].y]){
if(!q.empty()&&dis[q.front()]<dis[e[i].y]) q.push_front(e[i].y);
else q.push_back(e[i].y);
vis[e[i].y]=1;
}
}
}
vis[tn]=0;
}
return dis[s]!=-inf;
}
inline ll getcost(int x,ll flow){
vis[x]=1;ll f=0,d;
if(x==t) return flow;
for(int i=linkk[x];i;i=e[i].next){
if(!vis[e[i].y]&&e[i].flow&&dis[e[i].y]==dis[x]-e[i].w){
if(d=getcost(e[i].y,min(flow-f,e[i].flow))){
f+=d;e[i].flow-=d;e[e[i].back].flow+=d;
ans+=d*e[i].w;if(f==flow) return flow;
}
}
}
return f;
}
inline void zkw(){
while(spfa()){
vis[t]=1;
while(vis[t]){
for(int i=s;i<=t;i++) vis[i]=0;
getcost(s,inf);
}
}
}
int main(){
n=read();k=read();t1=read();t2=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) b[i]=read(),ans+=b[i];
s=0;t=n+1;
for(int i=1;i<=n;i++){
if(i+k<=n) insert(i,i+k,1,a[i]-b[i]);
else insert(i,t,1,a[i]-b[i]);
num[i]=len-1;
insert(i,i<n?i+1:t,k-t1-t2,0);
}
for(int i=2;i<=k;i++) insert(1,i,inf,0);
insert(s,1,k-t2,0);
zkw();
printf("%lld
",ans);
for(int i=1;i<=n;i++){
if(e[num[i]].flow) printf("E");
else printf("S");
}
return 0;
}