731. [网络流24题] 最长递增子序列★★★☆ 输入文件：alis.in 输出文件：alis.out 简单对比时间限制：1 s 内存限制：128 MB«问题描述：给定正整数序列x1,..., xn。（1）计算其最长递增子序列的长度s。（2）计算从给定的序列中最多可取出多少个长度为s的递增子序列。（3）如果允许在取出的序列中多次使用x1和xn，则从给定序列中最多可取出多少个长度为s的递增子序列。«编程任务：设计有效算法完成（1）（2）（3）提出的计算任务。«数据输入：由文件alis.in提供输入数据。文件第1 行有1个正整数n(n<=500)，表示给定序列的长度。接下来的1 行有n个正整数x1,..., xn。«结果输出:程序运行结束时，将任务（1）（2）（3）的解答输出到文件alis.out中。第1 行是最长递增子序列的长度s。第2行是可取出的长度为s 的递增子序列个数。第3行是允许在取出的序列中多次使用x1和xn时可取出的长度为s 的递增子序列个数。输入文件示例 输出文件示例alis.in43 6 2 5alis.out223
算法讨论：
首先求出dp[i]，表示1 ... i的最长不降子序列的长度。(本来是严格递增的，但是数据出挫了，成了不降了)
然后我们可以知道最长的不降子序列的长度 K，这是第一问的答案。接下来把每个i拆点，拆成<i, a> <i, b>对于每个i，如果有dp[i] = K，那么就insert(<i,b>, T, 1)的边。如果有dp[i] = 1, 那么就insert(S, <i, a>, 1)的边。然后insert(<i, a>, <i, b>, 1)的边。对于每一对 i < j，如果 dp[j] == dp[i] + 1 && a[i] <= a[j]，那么就insert(<i, b>, <j, a>, 1)的边。跑出的最大流就是第二问的答案。对于第三问，我们只要把第二问中对于<1> <n>的所有连边方式的容量都改成inf即可。黄学长说这个是分层图的思想，然后边的容量就是对取的次数的限制，由于第三问中x1 xn可以多次取，所以就把容量限制变成inf，相当于取消了次数限制。还要一个小细节就是如果第三问中流出的流量是 > n的，就输出n。这是因为可以无限的用x1 和 xn来构造最长的上升序列。总感觉这个题哪里怪怪的。代码：
#include#include #include #include #include #include using namespace std;const int N = 1000 + 5;const int oo = 0x3f3f3f3f;struct Edge { int from, to, cap, flow; Edge(int u = 0, int v = 0, int c = 0, int f = 0) : from(u), to(v), cap(c), flow(f) {}};struct Dinic { int nn, mm, s, t; int dis[N], cur[N], que[N * 10]; bool vis[N]; vector edges; vector G[N]; void clear() { for(int i = 0; i <= nn; ++ i) G[i].clear(); edges.clear(); } void add(int from, int to, int cap) { edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0)); mm = edges.size(); G[from].push_back(mm - 2); G[to].push_back(mm - 1); } bool bfs() { int head = 1, tail = 1; memset(vis, false, sizeof vis); dis[s] = 0; que[head] = s; vis[s] = true; while(head <= tail) { int x = que[head]; for(int i = 0; i < (signed) G[x].size(); ++ i) { Edge &e = edges[G[x][i]]; if(!vis[e.to] && e.cap > e.flow) { dis[e.to] = dis[x] + 1; vis[e.to] = true; que[++ tail] = e.to; } } ++ head; } return vis[t]; } int dfs(int x, int a) { if(x == t || a == 0) return a; int flw = 0, f; for(int &i = cur[x]; i < (signed) G[x].size(); ++ i) { Edge &e = edges[G[x][i]]; if(dis[e.to] == dis[x] + 1 && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) { e.flow += f; edges[G[x][i] ^ 1].flow -= f; a -= f; flw += f; if(!a) break; } } return flw; } int maxflow(int s, int t) { this->s = s; this->t = t; int flw = 0; while(bfs()) { memset(cur, 0, sizeof cur); flw += dfs(s, oo); } return flw; }}net;int n, S, T;int a[N], dp[N];#define stone_int main() {#ifndef stone_ freopen("alis.in", "r", stdin); freopen("alis.out", "w", stdout);#endif scanf("%d", &n); S = 0; T = (n << 1) | 1; net.nn = T; for(int i = 1; i <= n; ++ i) scanf("%d", &a[i]); dp[n] = 1; for(int i = 1; i <= n; ++ i) { dp[i] = 1; for(int j = 1; j < i; ++ j) if(a[i] >= a[j]) dp[i] = max(dp[i], dp[j] + 1); } int result = 0; for(int i = 1; i <= n; ++ i) result = max(result, dp[i]); for(int i = 1; i <= n; ++ i) { if(dp[i] == result) net.add(i + n, T, 1); if(dp[i] == 1) net.add(S, i, 1); net.add(i, i + n, 1); } for(int i = 1; i <= n ; ++ i) for(int j = i + 1; j <= n; ++ j) if(j != i) if(dp[j] == dp[i] + 1 && a[i] <= a[j]) net.add(i + n, j, 1); printf("%d\n%d\n", result, net.maxflow(S, T)); net.clear(); for(int i = 1; i <= n; ++ i) { int v = 1; if(i == 1 || i == n) v = oo; if(dp[i] == result) net.add(i + n, T, v); if(dp[i] == 1) net.add(S, i, v); net.add(i, i + n, v); } for(int i = 1; i <= n ; ++ i) for(int j = i + 1; j <= n; ++ j) if(j != i) if(dp[j] == dp[i] + 1 && a[i] <= a[j]) net.add(i + n, j, 1); int ans = net.maxflow(S, T); if(ans > n) printf("%d\n", n); else printf("%d\n", ans); #ifndef stone_ fclose(stdin); fclose(stdout);#endif return 0;}