BZOJ1283 序列 <费用流>

Problem

序列

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;162\;MB}$

Description

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

Input

第$1$行三个数$N,M,K$。 接下来$1$行$N$个正整数表示$C_i$。

Output

最大和。

Sample Input

10 5 3
4 4 4 6 6 6 6 6 4 4

Sample Output

30

HINT

$20\%$的数据: $N\le 10$。
$100\%​$的数据：$N\le 1000，K,M\le 100。C_i\le 20000​$。

Source

By YM

标签：费用流

Solution

常规费用流建模。
转化题意为：选$K​$次，每次选一个子序列，每一次连续$M​$个里面只能选一个。
对于第$i$个数$C_i$，

• 如果不选：$i\to i+1$ 流量$K$ 费用$0$
• 如果选，则下一个数在$i+M$之后：
  • 若$i\in [1, n-m]$：$i\to i+M$ 流量$1$ 费用$C_i$
  • 若$i\in (n-m, n]$：$i\to T$ 流量$1$ 费用$C_i$

特别地，有$S\to 1$ 流量$K$ 费用$0$；$N\to T$ 流量$K$ 费用$0$。
跑大费流即可。

Code

#include <bits/stdc++.h>
#define MAX_N 2000
#define MAX_M 100000
#define INF 0x7f7f7f7f
using namespace std;
int n, m, k, a[MAX_N+5];
int s, t, cnt, pr[MAX_N+5], cr[MAX_N+5], mxf, mic;
struct node {int v, c, w, nxt;} E[MAX_M+5];
void init() {s = 0, t = n+1, memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c, int w) {E[cnt] = (node){v, c, w, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c, int w) {insert(u, v, c, w), insert(v, u, 0, -w);}
bool SPFA() {
    queue <int> que;	bool inq[MAX_N+5];	int d[MAX_N+5], cr[MAX_N+5];
    memset(inq, false, sizeof inq), memset(d, INF, sizeof d);
    d[s] = 0, que.push(s), inq[s] = true, memset(cr, -1, sizeof cr);
    while (!que.empty()) {
        int u = que.front();	que.pop(), inq[u] = false;
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c, w = E[i].w;
            if (c && d[u]+w < d[v]) {
                d[v] = d[u]+w, cr[v] = i;
                if (!inq[v]) que.push(v), inq[v] = true;
            }
        }
    }
    if (d[t] == INF) return false;	int flow = INF;
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) flow = min(flow, E[i].c);
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) E[i].c -= flow, E[i^1].c += flow;
    mxf += flow, mic += d[t];	return true;
}
int main() {
    scanf("%d%d%d", &n, &m, &k), init();
    addedge(s, 1, k, 0), addedge(n, t, k, 0);
    for (int i = 1; i <= n; i++) scanf("%d", a+i);
    for (int i = 1; i < n; i++) addedge(i, i+1, k, 0);
    for (int i = 1; i <= n-m; i++) addedge(i, i+m, 1, -a[i]);
    for (int i = n-m+1; i <= n; i++) addedge(i, t, 1, -a[i]);
    while (SPFA()) ;	return printf("%d", -mic), 0;
}