首页 > 代码库 > BZOJ 1283: 序列

BZOJ 1283: 序列

2024-08-31 17:14:40   211人阅读

1283: 序列

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 272  Solved: 151
[Submit][Status][Discuss]

Description

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

Input

第1行三个数N,m,k。 接下来N行，每行一个字符串表示Ci。

Output

最大和。

Sample Input

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

Sample Output

30

HINT

20%的数据:n<=10。
100%的数据：N<=1000，k,m<=100。Ci<=20000。

Source

By YM

[Submit][Status][Discuss]

 

最大费用最大流

 

设立一个源点，一个汇点，源点向1连$<s,1,k,0>$的边（分别是出点，入点，流量，费用），n向汇点连$<n,t,k,0>$的边，1到n也用$<i,i+1,k,0>$的边连起来，限制最多流过k个流量。

1到n每个点$i$向$i+m$连一条$<i,i+m,1,num_{i}>$的边，表示选择这个数字，下次该流最少需要在$i+m$点之后选择下一个选择的数字。如果$i+m \gt n$，就向汇点连。

 

 1 #include <bits/stdc++.h> 2  3 const int inf = 1e9; 4 const int siz = 20005; 5  6 int n, m, k, num[siz]; 7  8 int s, t; 9 int hd[siz];10 int to[siz];11 int fl[siz];12 int vl[siz];13 int nt[siz];14 15 inline void add(int u, int v, int f, int w)16 {17     static int edge = 0, init = 1;18     if (init)memset(hd, -1, sizeof(hd)), init = 0;19     nt[edge] = hd[u]; to[edge] = v; fl[edge] = f; vl[edge] = +w; hd[u] = edge++;20     nt[edge] = hd[v]; to[edge] = u; fl[edge] = 0; vl[edge] = -w; hd[v] = edge++;21 }22 23 int pre[siz];24 int dis[siz];25 26 inline bool spfa(void)27 {28     static int que[siz], inq[siz], head, tail;29     for (int i = s; i <= t; ++i)dis[i] = -inf;30     memset(inq, 0, sizeof(inq));31     head = 0, tail = 0;32     que[tail++] = s;33     pre[s] = -1;34     dis[s] = 0;35     36     while (head != tail)37     {38         int u = que[head++], v; inq[u] = 0;39         40         for (int i = hd[u]; ~i; i = nt[i])41             if (dis[v = to[i]] < dis[u] + vl[i] && fl[i]) {42                 dis[v] = dis[u] + vl[i], pre[v] = i ^ 1;43                 if (!inq[v])inq[que[tail++] = v] = 1;44             }45     }46     47     return dis[t] > -inf;48 }49 50 inline int maxCost(void)51 {52     int cost = 0;53     54     while (spfa())55     {56         int flow = inf;57         58         for (int i = pre[t]; ~i; i = pre[to[i]])59             if (flow > fl[i ^ 1])flow = fl[i ^ 1];60             61         for (int i = pre[t]; ~i; i = pre[to[i]])62             fl[i] += flow, fl[i ^ 1] -= flow;63             64         cost += flow * dis[t];65     }66     67     return cost;68 }69 70 signed main(void)71 {72     scanf("%d%d%d", &n, &m, &k);73     74     for (int i = 1; i <= n; ++i)75         scanf("%d", num + i);76         77     s = 0, t = n + 1;78     79     add(s, 1, k, 0);80     add(n, t, k, 0);81     82     for (int i = 1; i < n; ++i)83         add(i, i + 1, k, 0);84         85     for (int i = 1; i <= n; ++i)86         if (i + m <= n)87             add(i, i + m, 1, num[i]);88         else89             add(i, t, 1, num[i]);90     91     printf("%d\n", maxCost());92 }

 

@Author: YouSiki

 

BZOJ 1283: 序列


联系
我们