差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:wangzai_milk:20200715比赛记录 [2020/07/16 16:52]
infinity37 [D - Distribution of books]
+++ 2020-2021:teams:wangzai_milk:20200715比赛记录 [2020/07/16 16:56] (当前版本)
infinity37 [I - K Subsequence]
@@ 行 358: / 行 358: @@
 </code></hidden>
 \\
+==== I - K Subsequence ====
+题意：给定一个数字序列，求k个不下降子序列，使得这些子序列的和最大。
+不下降子序列最大和好像是个比较经典的费用流模型，每个数字拆点，所有原点连这个数字前面的点，后面的点连汇点（流量1，费用0），两个点之间连流量为1，费用为$-a_i$的边，这个要找k个，那就在原点前面再连个超级原点，汇点后面来个超级汇点，流量为k即可。
+<hidden><code c++>
+#include <bits/stdc++.h>
+using namespace std;
+#define fi first
+#define se second
+typedef long long ll;
+const int INF = 1<<30;
+const int N = 4e3+20;
+typedef pair<int, int> pii;
+struct Edge {
+    int to, cap, cost, rev;
+    Edge() {}
+    Edge(int to, int _cap, int _cost, int _rev):to(to), cap(_cap), cost(_cost), rev(_rev) {}
+};
+int V;
+int h[N];
+int dis[N];
+int prevv[N];
+int pree[N];
+vector<Edge> G[N];
+void init(int n) {
+    V = n;
+    for(int i = 0; i <= V; ++i) G[i].clear();
+}
+void add(int x, int y, int cap, int cost){
+    G[x].push_back(Edge(y, cap, cost, G[y].size()));
+    G[y].push_back(Edge(x, 0, -cost, G[x].size() - 1));
+}
+int MCMF(int s, int t, int f, int &flow) {
+    int res = 0;
+    for(int i = 0; i < 1 + V; i++) h[i] = 0;
+    while(f){
+        priority_queue<pii, vector<pii>, greater<pii> > q;
+        for(int i = 0; i < 1 + V; i++) dis[i] = INF;
+        dis[s] = 0; q.push(pii(0, s));
+        while(!q.empty()) {
+            pii now = q.top(); q.pop();
+            int v = now.second;
+            if(dis[v] < now.first) continue;
+            for(int i = 0; i < G[v].size(); ++i) {
+                Edge &e = G[v][i];
+                if(e.cap > 0 && dis[e.to] > dis[v] + e.cost + h[v] - h[e.to]){
+                    dis[e.to] = dis[v] + e.cost + h[v] - h[e.to];
+                    prevv[e.to] = v;
+                    pree[e.to] = i;
+                    q.push(pii(dis[e.to], e.to));
+                }
+            }
+        }
+        if(dis[t] == INF) break;
+        for(int i = 0; i <= V; ++i) h[i] += dis[i];
+        int d = f;
+        for(int v = t; v != s; v = prevv[v]) d = min(d, G[prevv[v]][pree[v]].cap);
+        f -= d; flow += d; res += d * h[t];
+        for(int v = t; v != s; v = prevv[v]) {
+            Edge &e = G[prevv[v]][pree[v]];
+            e.cap -= d;
+            G[v][e.rev].cap += d;
+        }
+    }
+    return res;
+}
+int num[N];
+int main() {
+	int cas;
+	scanf("%d",&cas);
+	while (cas--)
+	{
+		int n,k;
+		scanf("%d%d",&n,&k);
+		int s = 2*n+1,t = 2*n+2;
+		int S = s+2,T = t+2;
+		init(n*2+4);
+		for (int i = 1;i<= n;i++)
+		{
+			scanf("%d",&num[i]);
+			add(s,i,1,0);
+			add(i+n,t,1,0);
+			add(i,i+n,1,-num[i]);
+		}
+		for (int i = 1;i<= n;i++)
+			for (int j = i+1;j<= n;j++)
+				if (num[j] >= num[i])
+					add(i+n,j,1,0);
+		add(S,s,k,0);add(t,T,k,0);
+		int flow = k;
+		printf("%d\n", -MCMF(S,T,INF,flow));
+	}
+	return 0;
+}
+</code></hidden>
+\\
 ==== K - Squrirrel ====

CVBB ACM Team

用户工具

站点工具

差别

页面工具