相关链接
题目传送门：https://contest.yandex.ru/neerc2016/contest/3529/problems/D/
敦敦敦题解：http://oi.cyo.ng/wp-content/uploads/2017/03/delight_for_a_cat_solution.pdf
一句话题意
有$n$天，每天只能睡觉或者吃饭，每天睡觉和吃饭的收益不同
要求连续$k$天中，至少有$ms$天睡觉，$me$天吃饭
求最大收益
解题报告
这题之前在绍一集训的时候考过
但当时并没有改题 QwQ
话说根据方程建费用流这个技能始终没在科技树上点亮啊
正解的话，其实也不难，就是瞎推一推式子
然后可以得到一个和志愿者招募那个题差不多的式子
于是我们撸一发费用流就可以啦！
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1009;
const int M = 5000;
const LL INF = 1e18;
int head[N],to[M],nxt[M],cost[M],flow[M];
int n,k,me,ms,S,T,s[N],e[N],edge[N];
LL vout,dis[N];
inline int Add_Edge(int u, int v, int f, int c) {
static int E = 1;
to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f; cost[E] = c;
to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0; cost[E] = -c;
return E - 1;
}
inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
class Minimum_Cost_Flow{
int sur[N],inq[N];
queue<int> que;
public:
inline LL MaxFlow() {
LL ret_cost = 0;
for (int f=1e9,w;SPFA();f=1e9) {
for (w=T;w!=S;w=to[sur[w]^1]) f = min(f, flow[sur[w]]);
for (w=T;w!=S;w=to[sur[w]^1]) flow[sur[w]] -= f, flow[sur[w]^1] += f;
ret_cost += dis[T] * f;
}
return ret_cost;
}
private:
bool SPFA() {
fill(dis, dis+N, INF);
que.push(S); dis[S] = 0;
while (!que.empty()) {
int w = que.front(); que.pop(); inq[w] = 0;
for (int i=head[w];i;i=nxt[i]) {
if (dis[to[i]] > dis[w] + cost[i] && flow[i]) {
dis[to[i]] = dis[w] + cost[i];
sur[to[i]] = i;
if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
}
}
}
return dis[T] < INF;
}
}MCMF;
int main() {
S = 0; T = N - 1;
n = read(); k = read();
ms = read(); me = read();
for (int i=1;i<=n;i++) vout += (s[i] = read());
for (int i=1;i<=n;i++) e[i] = read();
Add_Edge(S, n-k+2, k-ms, 0);
Add_Edge(1, T, k-ms, 0);
for (int i=2;i<=n-k+2;i++) Add_Edge(i, i-1, k-ms-me, 0);
for (int i=1;i<=n;i++) edge[i] = Add_Edge(min(i+1, n-k+2), max(1, i-k+1), 1, s[i] - e[i]);
printf("%lld\n",vout-MCMF.MaxFlow());
for (int i=1;i<=n;i++) putchar(flow[edge[i]]? 'S': 'E');
return 0;
}
It’s a pity you don’t have a donate button! I’d most certainly
donate to this outstanding blog! I suppose for now i’ll settle for book-marking and adding
your RSS feed to my Google account. I look forward to
fresh updates and will share this website with
my Facebook group. Chat soon!
We’re a bunch of volunteers and opening a brand new scheme in our community.
Your site offered us with valuable info to work
on. You’ve done a formidable process and our whole group shall be grateful to you.
I think this is among the most significant
information for me. And i am glad reading your article.
But want to remark on some general things, The site style is great, the articles is really nice : D.
Good job, cheers
Sweet blog! I found it while searching on Yahoo
News. Do you have any suggestions on how to get listed in Yahoo News?
I’ve been trying for a while but I never seem to get there!
Many thanks
I enjoy what you guys are up too. This type of clever work and
reporting! Keep up the awesome works guys I’ve included you guys to our blogroll.
I’m not sure exactly why but this blog is loading extremely slow for me.
Is anyone else having this issue or is it a issue on my end?
I’ll check back later on and see if the problem still
exists.
Hi there, I wish for to subscribe for this weblog to get latest updates, thus
where can i do it please help.
Does your site have a contact page? I’m having a tough time locating it but, I’d like to send you an e-mail. I’ve got some creative ideas for your blog you might be interested in hearing. Either way, great website and I look forward to seeing it expand over time.
I was suggested this web site by my cousin. I’m no longer sure whether
this post is written by way of him as no one else know such
special about my trouble. You are amazing!
Thanks!
Right away I am going to do my breakfast, afterward having my breakfast coming yet
again to read additional news.
495487 344372Id need to verify with you here. Which is not one thing I generally do! I take pleasure in reading a submit that will make individuals feel. In addition, thanks for permitting me to remark! 677149
Hello i am kavin, its my first time to commenting anyplace,
when i read this paragraph i thought i could also make comment due to
this good post.
104434 405749An attention-grabbing discussion is worth comment. I believe which you really should write more on this matter, it wont be a taboo topic however generally persons are not sufficient to talk on such topics. To the next. Cheers 433314
Hi there, I discovered your blog by means of Google even as looking for a related subject, your site came up, it appears to be like great.
I’ve bookmarked it in my google bookmarks.
Hello there, just turned into aware of your blog through Google, and found that it is truly informative.
I am gonna watch out for brussels. I’ll appreciate in the event you continue this in future.
A lot of folks will be benefited out of your writing.
Cheers!
72157 371410you use a great blog here! do you wish to have the invite posts in my small blog? 129127
Thank you for the auspicious writeup. It in fact was a amusement account it.
Look advanced to far added agreeable from you! However, how can we communicate?
My partner and I stumbled over here different web address and thought I should check things out.
I like what I see so now i am following you. Look forward to looking over your web page for
a second time.
I don’t even know how I finished up here, however I thought this post used to be great.
I don’t recognize who you’re however certainly you’re going to a famous blogger if you aren’t
already. Cheers!
Nice post. I was checking continuously this blog and I’m impressed!
Extremely useful info specially the last part 🙂 I care
for such info much. I was seeking this certain information for a long time.
Thank you and good luck.
I love reading an article that will make people think. Also,
thanks for allowing for me to comment!
Today, I went to the beach with my children. I found a sea shell and gave
it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She placed the shell to her ear and screamed.
There was a hermit crab inside and it pinched her ear.
She never wants to go back! LoL I know this
is completely off topic but I had to tell someone!
I think you have remarked some very interesting points, thankyou for the post.
A big thank you for your post.Thanks Again. Really Great.
Thanks-a-mundo for the article post.Really thank you! Want more.