Delight for a Cat

发表于 | 更新于

Link

Solution

默认每天都碎觉，每长度为KK的区间，可以把 天转化成歘饭。。

修改一个点ii，可以影响的区间的右端点的区间为[i,i+K−1][i,i+K-1]。

现在问题转化成有n−K+1n-K+1点和nn个区间，选择一个区间会产生相应获利，在每个点有[l,r][l,r]个区间覆盖着的前提下，获利尽量大。

建图 

1
2
3
4
S'->S <r,0>
S->1..k <1,0>
i->i+1 <r-l,0>
i->i+k <1,s[i]-e[i]>

对于i≥Ki\ge K,一个i->i+1的剖面，流量是r。把不改变的天数限制在[0,r-l]，那么改变的天数就满足了限制。

对于i<Ki<K，?

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
#include <cstdio>
#include <string>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
#define int64 long long
const int MAXN=1000+11;
template <class T> inline
bool chkmx(T &a,T const &b) {
	return a<b?a=b,1:0;
}
template <class T> inline
bool chkmn(T &a,T const &b) {
	return a>b?a=b,1:0;
}
namespace MCMF {
const int INF=0x1f1f1f1f;
const int64 INF64=0x1f1f1f1f1f1f1f1fll;
struct Edge {
	int to,v,cap,cost;Edge *pre,*rev;
	Edge(int to,int cap,int cost,Edge *pre):to(to),v(0),cap(cap),cost(cost),pre(pre),rev(0) {}
}*G[MAXN],*preE[MAXN];
int S,T,n;
int *Adde(int f,int t,int cap,int cost) {
	G[f]=new Edge(t,cap,cost,G[f]);
	G[t]=new Edge(f,0,-cost,G[t]);
	G[f]->rev=G[t];G[t]->rev=G[f];
	return &G[f]->v;
}
int Aug() {
	int minf=INF;
	for(Edge *e=preE[T];e;e=preE[e->rev->to]) {
		chkmn(minf,e->cap-e->v);
	}
	for(Edge *e=preE[T];e;e=preE[e->rev->to]) {
		e->v+=minf;
		e->rev->v-=minf;
	}
	return minf;
}
int64 dist[MAXN];
bool Path() {
	static bool inq[MAXN];
	static int Q[MAXN],he,ta;
	for(int i=0;i<=n;++i) {
		dist[i]=-INF64;
		inq[i]=0;
	}
	//队列有n+1个位置
	dist[S]=0;
	Q[he=0]=S;inq[S]=1;ta=1;
#define succ(i) ((i)==n?0:(i)+1)
	while(he!=ta) {
		int pos=Q[he];he=succ(he);inq[pos]=0;//丢人..
		for(Edge *e=G[pos];e;e=e->pre) if(e->cap>e->v) {
			int u=e->to;
			if(chkmx(dist[u],dist[pos]+e->cost)) {
				preE[u]=e;
				if(!inq[u]) {
					inq[u]=1;
					Q[ta]=u;
					ta=succ(ta);
				}
			}
		}
	}
	return dist[T]!=-INF64;
}
int64 Run() {
	int64 cost=0;
	int flow=0;
	while(Path()) {
		int f=Aug();
		flow+=f;
		cost+=dist[T]*f;
		//os<<cost<<'\n';
	}
	return cost;
}
/*namespace MCMF*/}
int main() {
	static int js[MAXN],je[MAXN],w[MAXN];
	int n,K,mSleep,mEat;
	is>>n>>K>>mSleep>>mEat;
	for(int i=1;i<=n;is>>js[i++]);
	for(int i=1;i<=n;is>>je[i++]);
	int64 sumjs=0;
	for(int i=1;i<=n;++i) {
		sumjs+=js[i];
		w[i]=je[i]-js[i];
	}
	static int *flow[MAXN];
	int limL=mEat,limR=K-mSleep;
	int SS=MCMF::S=0;
	int T=MCMF::T=n+1;
	int S=n+2;
	MCMF::n=n+3;
	//--K;
	MCMF::Adde(SS,S,limR,0);
	for(int i=1;i<=K;++i) {
		MCMF::Adde(S,i,0x1f1f1f1f,0);
	}
	for(int i=1;i<=n;++i) {
		MCMF::Adde(i,i+1,limR-limL,0);
		flow[i]=MCMF::Adde(i,std::min(i+K,T),1,w[i]);
	}
	os<<sumjs+MCMF::Run()<<'\n';
	for(int i=1;i<=n;++i) {
		os<<(*flow[i]?'E':'S');
	}os<<'\n';
	return 0;
}