非常经典的题目, 对于我来说难度颇大.
题目可以转化为
进行 \(K\) 次操作, 每次操作从这 \(N\) 个元素中选出一些元素, 其中任意两个元素的距离至少为 \(m\)
可以用费用流方法来做.
具体建模的方法:
S 连接到 \(1\) 点, 连接一条流量为 \(K\), 费用为 \(0\) 的边. 表示可以进行 \(K\) 次操作.
\(i\) 向 \(i+1\) 连一条流量为 \(inf\), 费用为 \(0\) 的边, 表示不选 \(i\) 这个点.(其实流量只要比 \(k\) 大就可以.
然后由 \(i\) 向 \(i+m\) 连接一条流量为 \(1\), 费用为 \(a_i\) 的边, 表示选择 \(i\) 这个点, 需要注意的是 \(i\) 点一定是小于等于 \(n - m\) 的. 其他的向 \(t\) 连相同的边.
然后跑一遍最大费用最大流.
这里的最大费用可以采用用最小费用跑, 但是把边权取反, 然后最后答案取反就可以了.
听说是线性规划裸题, 但是我不知道什么是线性规划.
懒得写板子了, 抄了一份上古时代写的.
- /*header*/
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- #include <vector>
- #include <cmath>
- #include <map>
- #include <queue>
- #define gc getchar()
- #define pc putchar
- #define ll long long
- #define mk make_pair
- #define fi first
- #define se second
- using std::min;
- using std::max;
- using std::swap;
- const int inf = 0x3f3f3f3f;
- inline int gi() {
- int x = 0,f = 1;char c = gc;
- while(c <'0' || c> '9') {if(c == '-')f = -1;c = gc;}
- while(c>= '0' && c <= '9') {x = x * 10 + c - '0';c = gc;}return x * f;
- }
- const int maxN = 5000 + 7;
- const int maxM = 100000 + 7 ;
- using namespace std;
- int n, m, s, t, ans, maxflow, k;
- int head[maxN];
- struct Node{
- int u,v,flow,spend,nex;
- }Map[maxM];
- int dis[maxN],vis[maxN],num,path[maxN];
- void init() {
- s = n + 1;
- t = s + 1;
- num = -1;
- memset(head,-1,sizeof(head));
- return;
- }
- void add_Node(int u,int v,int w,int spend) {
- Map[++ num] = (Node) {u , v, w, spend, head[u]};head[u] = num;
- Map[++ num] = (Node) {v , u, 0, -spend, head[v]};head[v] = num;
- return ;
- }
- bool spfa() {
- queue<int>q;
- q.push(s);
- memset(dis,0x3f,sizeof(dis));
- memset(path,0,sizeof(path));
- dis[s] = 0;
- vis[s] = true;
- while(!q.empty()) {
- int p = q.front();q.pop();
- vis[p] = false;
- for(int i = head[p];i != -1;i = Map[i].nex) {
- int v = Map[i].v;
- if(dis[v]> dis[p] + Map[i].spend && Map[i].flow) {
- dis[v] = dis[p] + Map[i].spend;
- path[v] = i;
- if(!vis[v]) {
- q.push(v);
- vis[v] = true;
- }
- }
- }
- }
- if(dis[t] == 0x3f3f3f3f) return false;
- return true;
- }
- int min(int a,int b) {return a> b ? b : a ;}
- void f() {
- int mn = 0x7fffffff;
- for(int i = t;i != s;i = Map[path[i]].u)
- mn = min(mn,Map[path[i]].flow);
- ans += mn;
- for(int i = t;i != s;i = Map[path[i]].u) {
- Map[path[i]].flow -= mn;
- Map[path[i] ^ 1].flow += mn;
- maxflow += mn * Map[path[i]].spend;
- }
- }
- void EK() {
- while(spfa())
- f();
- printf("%d",-maxflow);
- return ;
- }
- int a[maxN];
- int main() {
- n = gi();m = gi();k = gi();
- init();
- for(int i = 1;i <= n;++ i) a[i] = gi();
- for(int i = 1;i < n;++ i) add_Node(i , i + 1, k + 2, 0);
- add_Node(s , 1, k, 0); add_Node(n , t, k + 2, 0);
- for(int i = 1;i <= n - m;++ i) add_Node(i , i + m, 1, -a[i]);
- for(int i = n - m + 1;i <= n;++ i) add_Node(i , t, 1, -a[i]);
- EK();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2948436.html