OJ-Problems-Source/HDOJ/4106_autoAC.cpp

102 lines
2.6 KiB
C++
Raw Permalink Normal View History

#include<cstdio>
#include<stdlib.h>
#include<cstring>
using namespace std;
const int inf=99999999;
struct{
int v, cap, cost, next, re;
}edge[10005];
int n,ans;
int k,edgeHead[1050];
int que[10050],pre[1050],dis[1050];
bool vis[1050];
int wei[1050];
int min(int a,int b){
return a>b?b:a;
}
int max(int a,int b){
return a>b?a:b;
}
void addEdge(int u,int v,int ca,int co){
edge[k].v=v;
edge[k].cap=ca;
edge[k].cost=co;
edge[k].next=edgeHead[u];
edge[k].re=k + 1;
edgeHead[u]=k ++;
edge[k].v=u;
edge[k].cap=0;
edge[k].cost=-co;
edge[k].next=edgeHead[v];
edge[k].re=k - 1;
edgeHead[v]=k ++;
}
bool spfa(){
int i, head = 0, tail = 1;
for(i = 0; i <= n; i ++){
dis[i] = inf;
vis[i] = false;
}
dis[0] = 0;
que[0] = 0;
vis[0] = true;
while(head != tail){
int u = que[head];
for(i = edgeHead[u]; i != 0; i = edge[i].next){
int v = edge[i].v;
if(edge[i].cap && dis[v] >dis[u] + edge[i].cost){
dis[v] = dis[u] + edge[i].cost;
pre[v] = i;
if(!vis[v]){
vis[v] = true;
que[tail ++] = v;
if(tail == 10000) tail = 0;
}
}
}
vis[u] = false;
head++;
if(head ==10000) head = 0;
}
if(dis[n] ==inf) return false;
return true;
}
void end(){
int u, p;
for(u = n; u != 0; u = edge[edge[p].re].v){
p = pre[u];
edge[p].cap -= 1;
edge[edge[p].re].cap += 1;
ans += edge[p].cost;
}
}
int main(){
int i,j,v,lim,m,sum;
while(scanf("%d %d %d",&v,&m,&lim)!=EOF){
k=1;
sum=0;
memset(edgeHead,0,sizeof(edgeHead));
for(i=1;i<=v;i++){
scanf("%d",&wei[i]);
sum+=wei[i];
}
if(m<=lim){
printf("%d\n",sum);
continue;
}
n=v-m+2;
for(i=0;i<=n;i++){
addEdge(i,i+1,lim,0);
}
for(i=1;i<=v;i++){
addEdge(max(1,i-m+1),min(n-1,i)+1,1,-wei[i]);
}
ans=0;
n++;
while(spfa())
end();
printf("%d\n",-ans);
}
return 0;
}