记录编号	167927	评测结果	AAAAAAAAAAAA
题目名称	[网络流24题] 餐巾	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.033 s
提交时间	2015-06-29 19:21:17	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<deque>
using namespace std;
const int SIZEN=210;
const int INF=0x7fffffff/2;
int N;
int price;
int slow_cost,slow_wait,fast_cost,fast_wait;
int need[SIZEN]={0};
deque<pair<int,int> > can_slow,can_fast,late;//first是日期,second是个数
int calc(int buy){//购买buy个
	int ans=buy*price;
	can_fast.clear();can_slow.clear();late.clear();
	for(int i=1;i<=N;i++){
		while(!late.empty()&&late.front().first<=i-fast_wait){
			can_fast.push_back(late.front());
			late.pop_front();
		}
		while(!can_fast.empty()&&can_fast.front().first<=i-slow_wait){
			can_slow.push_back(can_fast.front());
			can_fast.pop_front();
		}
		int now=need[i];
		int t=min(now,buy);
		now-=t,buy-=t;
		while(now&&!can_slow.empty()){
			t=min(now,can_slow.back().second);
			ans+=t*slow_cost;
			now-=t,can_slow.back().second-=t;
			if(!can_slow.back().second) can_slow.pop_back();
		}
		while(now&&!can_fast.empty()){
			t=min(now,can_fast.back().second);
			ans+=t*fast_cost;
			now-=t,can_fast.back().second-=t;
			if(!can_fast.back().second) can_fast.pop_back();
		}
		if(now) return INF;
		late.push_back(make_pair(i,need[i]));
	}
	return ans;
}
void work(void){
	int buy=0,ans=INF;
	for(int i=1;i<=N;i++) buy+=need[i];
	while(buy){
		int now=calc(buy);
		if(now==INF) break;
		ans=min(ans,now);
		buy--;
	}
	printf("%d\n",ans);
}
void read(void){
	scanf("%d",&N);
	for(int i=1;i<=N;i++) scanf("%d",&need[i]);
	scanf("%d",&price);
	scanf("%d%d",&fast_wait,&fast_cost);
	scanf("%d%d",&slow_wait,&slow_cost);
}
int main(){
	freopen("napkin.in","r",stdin);
	freopen("napkin.out","w",stdout);
	read();
	work();
	return 0;
}