记录编号	430026	评测结果	AAAAAAAAAAAA
题目名称	[网络流24题] 餐巾	最终得分	100
用户昵称	xyz117	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2017-07-29 09:31:29	内存使用	0.38 MiB

#include<stdio.h>
#include<string.h>
using namespace std;
#define INF 0x7fffffff
#define maxn 301
#define maxm 1201
#define min(a,b) a<b?a:b
struct node
{
	int v,f,w,nex;
}edge[maxm<<1];
int pre[maxn<<1],tot=1;
int s[maxn];
void add(int u,int v,int f,int w)
{
	edge[++tot]=(node){v,f,w,pre[u]};
	pre[u]=tot;
	edge[++tot]=(node){u,0,-w,pre[v]};
	pre[v]=tot;
}
int q[(maxm<<3)+(maxm<<1)],d[maxn<<1];
bool book[maxn<<1];
int anst,ansl,head,tail;
int n,m;
int S,T;
bool spfa()
{
	memset(book,false,sizeof(book));
	int i,x,v;
	for(i=0;i<=n+n+1;i++)
		d[i]=INF;
	head=0,tail=1;
	q[0]=T;
	d[T]=0;
	book[T]=true;
	while(head<tail)
	{
		x=q[head],head++;
		for(i=pre[x];i;i=edge[i].nex)
		{
			v=edge[i].v;
			if(edge[i^1].f&&d[x]-edge[i].w<d[v])
			{
				d[v]=d[x]-edge[i].w;
				if(!book[v])
				{
					q[tail++]=v;
					book[v]=true;
				}
			}
		}
		book[x]=false;
	}
	return d[S]!=INF;
}
int dfs(int x,int low)
{
	book[x]=1;
	if(x==T)
		return low;
	int v,i,w,u=0;
	for(i=pre[x];i;i=edge[i].nex)
	{
		v=edge[i].v;
		if(edge[i].f&&!book[v]&&d[v]==d[x]-edge[i].w)
		{
			w=dfs(v,min(low-u,edge[i].f));
			ansl+=w*edge[i].w;
			u+=w;
			edge[i].f-=w;
			edge[i^1].f+=w;
			if(u==low)
				return low;
		}
	}
	return u;
}
void zkw()
{
	int tmp=0;
	while(spfa())
	{
		book[T]=1;
		while(book[T])
		{
			memset(book,false,sizeof(book));
			dfs(S,INF);
		}
	}
}
int read()
{
	char s=getchar();
	int a=0,flag=1;
	while(s<'0'||s>'9')
	{
		if(s=='-')
			flag=-1;
		s=getchar();
	}
	while(s>='0'&&s<='9')
	{
		a=a*10+s-'0';
		s=getchar();
	}
	return flag*a;
}
int main()
{
	freopen("napkin.in","r",stdin);
	freopen("napkin.out","w",stdout);
	int c1,c2,c3,d1,d2;
	n=read();
	S=0;
	T=n+n+1;
	for(int i=1;i<=n;i++)
		s[i]=read();
	c1=read(),d1=read(),c2=read(),d2=read(),c3=read();
	for(int i=1;i<=n;i++)
	{
		add(S,i,s[i],0);
		add(i+n,T,s[i],0);
		add(S,i+n,INF,c1);
		if(i<n)
			add(i,i+1,INF,0);
		if(i+d1<=n)
			add(i,i+n+d1,INF,c2);
		if(i+d2<=n)
			add(i,i+n+d2,INF,c3);
	}
	zkw();
	printf("%d",ansl);
}