「bzoj1283」序列 - 费用流+一维模型 | Bill Yang's Blog
0%

「bzoj1283」序列 - 费用流+一维模型

题目大意

    给出一个长度为$N$的正整数序列$C_i$,求一个子序列,使得原序列中任意连续长度为$M$的子串中被选出的元素不超过$K(K,M\le100)$个,并且选出的元素之和最大。


题目分析

照抄姜志豪题解。

将原问题进行转化:可以在序列中从左往右选择$k$次,但在同一次选择中,任意一个长度为$m$的连续子序列最多选择一个元素。
这样我们就可以建立出下图的模型:


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=1005;

struct Edge {
int from,to,cap,flow,cost;
Edge(int x=0,int y=0,int c=0,int f=0,int co=0):from(x),to(y),cap(c),flow(f),cost(co) {}
};

struct zkw_CostFlow {
int n,m,s,t;
vector<Edge>edges;
vector<int>G[maxn];
bool inque[maxn],vst[maxn];
int path[maxn],dist[maxn];
int flow,cost;
void init(int n) {
this->n=n;
edges.clear();
for(int i=1; i<=n; i++)G[i].clear();
}
void AddEdge(int x,int y,int v,int f) {
edges.push_back(Edge(x,y,v,0,f));
edges.push_back(Edge(y,x,0,0,-f));
m=edges.size();
G[x].push_back(m-2);
G[y].push_back(m-1);
}
bool spfa() {
for(int i=1; i<=n; i++)dist[i]=-INT_MAX/2;
memset(inque,0,sizeof(inque));
dist[t]=0;
inque[t]=1;
deque<int>Q;
Q.push_back(t);
while(!Q.empty()) {
int Now=Q.front();
Q.pop_front();
inque[Now]=0;
for(int id:G[Now]) {
Edge& e=edges[id^1];
int Next=e.from;
if(dist[Next]<dist[Now]+e.cost&&e.cap>e.flow) {
dist[Next]=dist[Now]+e.cost;
if(!inque[Next]) {
inque[Next]=1;
if(!Q.empty()&&dist[Next]>dist[Q.front()])Q.push_front(Next);
else Q.push_back(Next);
}
}
}
}
return dist[s]>-INT_MAX/2;
}
int dfs(int Now,int a) {
if(vst[Now])return 0;
if(Now==t||a==0)return a;
int flow=0;
vst[Now]=1;
for(int id:G[Now]) {
Edge& e=edges[id];
int Next=e.to;
if(dist[Now]-e.cost!=dist[Next])continue;
int nextflow=dfs(Next,min(a,e.cap-e.flow));
if(nextflow>0) {
cost+=nextflow*e.cost;
e.flow+=nextflow;
edges[id^1].flow-=nextflow;
flow+=nextflow;
a-=nextflow;
if(a==0)break;
}
}
return flow;
}
int maxflow(int s,int t) {
this->s=s;
this->t=t;
flow=cost=0;
while(spfa()) {
memset(vst,0,sizeof(vst));
flow+=dfs(s,INT_MAX);
}
return flow;
}
} zkw;

int n,m,k;

int main() {
n=Get_Int();
m=Get_Int();
k=Get_Int();
int S=n+1,T=n+2;
zkw.init(T);
zkw.AddEdge(S,1,k,0);
zkw.AddEdge(n,T,k,0);
for(int i=1; i<=n; i++) {
if(i>1)zkw.AddEdge(i-1,i,k,0);
if(i+m<=n)zkw.AddEdge(i,i+m,1,Get_Int());
else zkw.AddEdge(i,T,1,Get_Int());
}
zkw.maxflow(S,T);
printf("%d\n",zkw.cost);
return 0;
}
姥爷们赏瓶冰阔落吧~