BZOJ1283 序列 <费用流>

Problem

序列

Description

给出一个长度为的正整数序列，求一个子序列，使得原序列中任意长度为的子串中被选出的元素不超过个，并且选出的元素之和最大。

Input

第行三个数。接下来行个正整数表示。

Output

最大和。

Sample Input

1 2	10 5 3 4 4 4 6 6 6 6 6 4 4

Sample Output

HINT

的数据: 。
的数据：。

Source

By YM

标签：费用流

Solution

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

如果不选：流量费用
如果选，则下一个数在之后：
- 若：流量费用
- 若：流量费用

特别地，有流量费用；流量费用。
跑大费流即可。

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;
}