首页 > 代码库 > vijosP1499炸毁燃料库

vijosP1499炸毁燃料库

背景

某天,外星人展开了对地球的侵略,OIer们开始与之周旋。。。

描述

外星人派出了172849个外星人乘着UFO来到地球,curimit神new带领着OIer们奋力抵抗。curimit神new觉得,仅仅抵抗外星人是不行的,因为外星人还有172849架UFO,必须从根源阻止外星人!
于是curimit神new交给小z一个任务:潜入外星人的基地,摧毁外星人的燃料库。

小z拿着curimit神new给他的地图,来到了外星人的基地。

外星人的燃料库由一排N个燃料筒组成,每个燃料筒中装有一些燃料。小z需要用炸弹炸毁燃料筒。有的燃料筒里面有许多燃料,炸毁它价值就比较高。但有的燃料筒里面只有很少的燃料,甚至没有燃料,所以炸毁它价值很低,甚至不值得去炸毁!于是curimit神new对每个燃料筒有一个估价,有正有负。但是外星人也不是没有防范。在燃料库中有172849个外星人在不停的巡逻,如果小z把任意连续M个燃料筒炸毁K个以上,外星人就会察觉,小z就遭殃了!
于是小z希望你能够帮他定出一个方案,在不被外星人察觉的情况下,能够使自己炸毁的燃料筒的估价和最大(如果所有筒的估价都是负的,那么一个不炸的估价和最大,是0)。

格式

输入格式

第一行有三个数,N,M,K。N<=1000,k<=m<=100。描述见题。

第二行有N个整数,绝对值小于1000,第i个数表示curimit神new对第i个燃料筒的估价。

输出格式

一个数,为满足条件的最大估价和。

题解:
p1499=ontak2010 vacation =p1891
我想说出题人为什么出这么明显的原题。。。。
代码:
 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 10000014 #define maxm 10000015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 100000000723 using namespace std;24 inline int read()25 {26     int x=0,f=1;char ch=getchar();27     while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();}28     while(ch>=0&&ch<=9){x=10*x+ch-0;ch=getchar();}29     return x*f;30 }31 int n,m,k,mincost,tot=1,s,t,a[maxn],head[maxn],q[maxm],d[maxn],from[2*maxm];32 bool v[maxn];33 struct edge{int from,next,go,v,c;}e[2*maxm];34 void ins(int x,int y,int z,int w)35 {36     e[++tot].go=y;e[tot].from=x;e[tot].v=z;e[tot].c=w;e[tot].next=head[x];head[x]=tot;37 }38 void insert(int x,int y,int z,int w)39 {40     ins(x,y,z,w);ins(y,x,0,-w);41 }42 bool spfa()43 {44     for (int i=s;i<=t;i++){v[i]=0;d[i]=inf;}45     int l=0,r=1,y;q[1]=s;d[s]=0;v[0]=1;46     while(l!=r)47     {48         int x=q[++l];if(l==maxn)l=0;v[x]=0;49         for (int i=head[x];i;i=e[i].next)50          if(e[i].v&&d[x]+e[i].c<d[y=e[i].go])51          {52             d[y]=d[x]+e[i].c;from[y]=i;53             if(!v[y]){v[y]=1;q[++r]=y;if(r==maxn)r=0;}54          }55     }56     return d[t]!=inf;57 }58 void mcf()59 {60     while(spfa())61     {62         int tmp=inf;63         for(int i=from[t];i;i=from[e[i].from]) tmp=min(tmp,e[i].v);64         mincost+=d[t]*tmp;65         for(int i=from[t];i;i=from[e[i].from]){e[i].v-=tmp;e[i^1].v+=tmp;}66     }67 }68 int main()69 {70     freopen("input.txt","r",stdin);71     freopen("output.txt","w",stdout);72     n=read();m=read();k=read();73     s=0;t=n+1;74     for1(i,n)a[i]=read();75     insert(s,1,k,0);insert(n-m+2,t,k,0);76     for1(i,m)insert(1,i+1,1,-a[i]);77     for2(i,m+1,n-m)insert(i-m+1,i+1,1,-a[i]);78     for2(i,n-m+1,n)insert(i-m+1,n-m+2,1,-a[i]);79     for1(i,n-m+1)insert(i,i+1,inf,0);80     mcf();81     printf("%d\n",-mincost);82     return 0;83 }
View Code

 

vijosP1499炸毁燃料库