Delight for a Cat[bzoj4842]

发表于 分类于

题目链接

vjudge

题解

首先你可以先强制令所有时间都打隔膜。那么如果某个时间点变为了睡觉，那么收益就为 $c_i=a_i-b_i$。

然后令 $x_i$ 表示每个时间段是否变为睡觉，那么有：

$$\forall j\in [1,n-k+1],t_1\leq \sum_{i=j}^{j+k-1} x_i\leq k-t_2$$

根据线性规划的那套东西，我们再设变量 $y_i$，将不等式变为等式：

$$\forall j\in [1,n-k+1],\sum_{i=j}^{j+k-1} x_i+y_j-t_1=0,y_j\leq k-t_1-t_2$$

再这 $n-k+1$ 个方程后面添加 $0=0$，然后差分得到：

$$x_1+x_2+\cdots+x_k+y_1-t_1=0 \ x_{k+1}-x_1+y_2-y_1=0 \ x_{k+2}-x_2+y_3-y_2=0 \ \vdots \ x_n-x_{n-k}+y_{n-k+1}-y_{n-k}=0 \ -x_{n-k+1}-x_{n-k+2}-\cdots-x_n-y_{n-k+1}+t_1=0$$

最后要使得 $\sum x_ic_i$ 最大。

然后你发现每个变量都只出现了两遍，且系数为 $1$ 和 $-1$。

那么把每个方程看做一个点，每个变量从系数为 $1$ 的点连向 $-1$ 的点。对于 $x_i$，流量为 $1$，费用为 $c_i$；对于 $y_i$，流量为 $k-t_1-t_2$，费用为 $0$。因为网络流有个非常好的就是除了源汇点之外，流入=流出。这样连边就相当于保证了变量的上限以及变量的守恒。

然后跑最大费用最大流就好了。

程序

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
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int M=40010;
const int N=10005;
const ll inf=1e18;
namespace MCMF{
	int ver[M],val[M],ne[M],cost[M],head[N],tot=1;
	int s,t;
	ll d[N];
	int mi[N],pre[N];
	bool vis[N];
	queue<int> q;
	inline void add(int x,int y,int v,int c)
	{
		ver[++tot]=y; val[tot]=v; cost[tot]=c; ne[tot]=head[x]; head[x]=tot;
		ver[++tot]=x; val[tot]=0; cost[tot]=-c;ne[tot]=head[y]; head[y]=tot;
	}
	inline bool spfa()
	{
		fo(i,0,t) d[i]=-inf,vis[i]=pre[i]=mi[i]=0;
		d[s]=0; pre[s]=0; mi[s]=2e9;
		q.push(s); vis[s]=1;
		for(int u;!q.empty();)
		{
			u=q.front(); q.pop(); vis[u]=0;
			for(int i=head[u],v;i;i=ne[i])
			if(val[i]&&d[v=ver[i]]<d[u]+cost[i])
			{
				d[v]=d[u]+cost[i]; pre[v]=i; mi[v]=min(mi[u],val[i]);
				if(!vis[v]) q.push(v),vis[v]=1;
			}
		}
		return mi[t];
	}
	inline ll work()
	{
		ll ans=0;
		while(spfa())
		{
			ans+=1ll*d[t]*mi[t];
			for(int v=t;v;v=ver[pre[v]^1]) val[pre[v]]-=mi[t],val[pre[v]^1]+=mi[t];
		}
		return ans;
	}
}
ll sum;
int n,k,t1,t2,a[N],b[N],pos[N];
int main()
{
	n=read(); k=read(); t1=read(); t2=read();
	fo(i,1,n) a[i]=read();
	fo(i,1,n) b[i]=read(),sum+=b[i];
	MCMF::s=0; MCMF::t=n-k+3;
	MCMF::add(MCMF::s,1,k-t2,0);
	MCMF::add(n-k+2,MCMF::t,k-t2,0);
	fo(i,1,n) MCMF::add(max(1,i-k+1),min(i+1,n-k+2),1,a[i]-b[i]),pos[i]=MCMF::head[max(1,i-k+1)];
	fo(i,1,n-k+1) MCMF::add(i,i+1,k-t1-t2,0);
	printf("%lld\n",sum+MCMF::work());
	fo(i,1,n) putchar(MCMF::val[pos[i]]?'E':'S');
	return 0;
}