题目传送门：http://cojs.tk/cogs/problem/problem.php?pid=461
建图方法是：
将每天的输入和输出拆点，建成二分图的样子
然后搞一搞，详见Sengxian’s Blog
之前直接建成时间线来跑，结果血wa
后来发现，那么建图根本没法保证每一天满流啊！
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 10000;
const int INF = 100000000;
int head[N],nxt[N],to[N],cost[N],flow[N],dis[N],inq[N];
int n,st,sc,ft,fc,arr[N],S,T,p,sur[N],FLOW[N];
queue<int> que;
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;
}
#define id(x,ty) ((x)*2+ty)
inline void Add_Edge(int u, int v, int f, int c) {
static int TT = 1;
to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f; cost[TT] = c;
to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0; cost[TT] = -c;
}
inline int SPFA() {
memset(dis,127,sizeof(dis));
memset(FLOW,0,sizeof(FLOW));
que.push(S); dis[S] = 0; inq[S] = 1; FLOW[S] = INF;
while (!que.empty()) {
int w = que.front(); que.pop(); inq[w] = 0;
for (int i=head[w];i;i=nxt[i]) if (flow[i] && dis[w] + cost[i] < dis[to[i]]) {
dis[to[i]] = dis[w] + cost[i]; sur[to[i]] = i;
FLOW[to[i]] = min(FLOW[w], flow[i]);
if (!inq[to[i]]) que.push(to[i]), inq[to[i]] = 1;
}
} return FLOW[T];
}
inline int MCMF() {
int ret = 0;
for (int w=T,f;f=SPFA();w=T)
for (int t=sur[w];w!=S;t=sur[w])
flow[t] -= f,
flow[t^1] += f,
ret += cost[t]*f,
w = to[t^1];
return ret;
}
int main(){
freopen("napkin.in","r",stdin);
freopen("napkin.out","w",stdout);
n = read(); S = 0; T = 1;
for (int i=1;i<=n;i++) arr[i] = read();
p = read(); ft = read(); fc = read(); st = read(); sc = read();
for (int i=1;i<=n;i++) Add_Edge(S,id(i,0),arr[i],0), Add_Edge(id(i,1),T,arr[i],0);
for (int i=1;i<n;i++) Add_Edge(id(i,0),id(i+1,0),INF,0);
for (int i=1;i<=n;i++) if (i + ft <= n) Add_Edge(id(i,0),id(i+ft,1),INF,fc);
for (int i=1;i<=n;i++) if (i + st <= n) Add_Edge(id(i,0),id(i+st,1),INF,sc);
for (int i=1;i<=n;i++) Add_Edge(S,id(i,1),INF,p);
printf("%d\n",MCMF());
return 0;
}
I like it when individuals get together and share thoughts.
Great website, continue the good work!
I believe that is one of the so much vital information for me.
And i’m satisfied studying your article. But wanna
remark on some normal things, The site style is wonderful,
the articles is actually nice : D. Just right job, cheers
I do not even know how I ended up here, but I thought this post
was good. I do not know who you are but definitely you are going to a famous blogger if you are not already 😉 Cheers!
Actually when someone doesn’t understand then its up to other people
that they will help, so here it takes place.
It is in reality a nice and helpful piece of info. I am satisfied that
you simply shared this helpful information with us.
Please stay us up to date like this. Thank you for sharing.
Fantastic blog! Do you have any tips and hints
for aspiring writers? I’m hoping to start my own website soon but I’m a little
lost on everything. Would you recommend starting with a free platform like WordPress
or go for a paid option? There are so many options out there that I’m completely
confused .. Any tips? Kudos!
Touche. Sound arguments. Keep up the great work.
hello there and thank you for your info – I have definitely picked up something
new from right here. I did however expertise a few technical issues using this
site, as I experienced to reload the web site many times previous to I could get it to load properly.
I had been wondering if your web host is OK? Not that I am complaining,
but sluggish loading instances times will sometimes affect your placement in google and can damage your quality score if advertising
and marketing with Adwords. Well I’m adding this RSS to my email and can look
out for much more of your respective intriguing content.
Ensure that you update this again very soon.
Thank you a bunch for sharing this with all of us you really
recognise what you are talking approximately! Bookmarked.
Please additionally discuss with my website =).
We will have a link alternate arrangement between us
Hello! I’ve been reading your website for a while now and
finally got the courage to go ahead and give
you a shout out from Huffman Tx! Just wanted to tell you keep up the fantastic job!
top online usa casinos
vegas casino online
real money online casinos usa
online payday loans
online payday loan
cash advance on credit card
Appreciating the commitment you put into your blog and in depth
information you provide. It’s great to come across a blog every once in a
while that isn’t the same old rehashed information. Excellent read!
I’ve bookmarked your site and I’m adding your RSS feeds to my Google
account.
Hello Dear, are you actually visiting this site daily, if so afterward you
will definitely get pleasant knowledge.
I do not know whether it’s just me or if everyone
else experiencing issues with your site. It looks like some of the written text
in your posts are running off the screen. Can somebody else please comment and let me know
if this is happening to them as well? This might be a issue with my internet browser because I’ve had
this happen previously. Many thanks
bookmarked!!, I like your website!
Remarkable! Its in fact awesome piece of writing, I have got much clear idea regarding from
this article.
Fantastic beat ! I would like to apprentice even as you amend
your web site, how can i subscribe for a
weblog web site? The account aided me a appropriate deal.
I were a little bit acquainted of this your broadcast provided brilliant transparent concept
Hello! Do you use Twitter? I’d like to follow you if that
would be okay. I’m undoubtedly enjoying your blog and look forward to new posts.
What’s up to every body, it’s my first go to
see of this website; this weblog consists of awesome and
genuinely good data for readers.
Very nice post. I just stumbled upon your blog and wished to say that I’ve truly enjoyed browsing your blog posts.
After all I will be subscribing to your feed and I hope you write again very soon!
Very descriptive article, I enjoyed that a lot.
Will there be a part 2?
Hi! I’ve been following your site for some time now and finally got the courage to go ahead and give you a shout out
from New Caney Tx! Just wanted to mention keep
up the great work!
You could definitely see your skills within the article you write.
The world hopes for even more passionate writers such as you who are not afraid to say how
they believe. At all times go after your heart.
Good site you’ve got here.. It’s hard to find good
quality writing like yours these days. I truly appreciate
individuals like you! Take care!!