这道题刚开始尝试自己写网络流，然后改来改去最终就写炸了……然后就看了题解，发现好多篇题解都是由一篇衍生出来的……甚至笔误都是一样。
所以我参照完题解后还是觉得应该自己写一篇最能让人看懂的题解。
首先，第一问就是比较简单的dp，不过我们令dp[i]表示以a[i]结尾（不是到第 i 位）的最长不下降子序列的长度，为什么这么写请看下文。然后答案就是len = max(dp[i])。
接下来考虑下两问：
对于第二问：
1.因为每一个点只能用一次，所以自然想到把 i 拆成 i 和 i +n，然后连一条从 i 到 i + n，容量为1的边，然后对于一个点 i ，一定是从 i 进入，i + n 出来，这样就保证 i 只使用一次了。
2.遍历 i :1~n,若dp[i] = 1，说明某一个子序列一定从这开始，就连一条从源点到 i ，容量为1的边；若dp[i] = len，说明序列中其中一条最长的不下降子序列在这里结束了，就连一条从 i 到汇点，容量为1的边。
3.最后考虑的就是点和点之间怎么转化（也就是怎么建边）：若 i > j && a[i] >= a[j] && dp[i] = dp[j] +1，就说明a[i]和a[j]可以是某一个不下降子序列中相邻的两项，那么就从 j + n 到 i 连一条容量为1的边。
然后跑最大流就行了~~
第三问：
只要把第二问的图改一下就行：
1.对于节点1：因为dp[1]一定等于1，所以建一条从源点到1，容量为INF的边，然后在建一条1到1+n，容量为INF的边。
2.对于节点 n：首先还是建一条从n到n + n，容量为INF的边。不过dp[n]不一定等于n，所以如果等于n的话，才建一条从n到汇点，容量为INF的边。
这些修改只要在原来的残量网络上修改就行，然后跑一下最大流，答案是第二问加上这一次的答案。
1 #include<cstdio>
2 #include<iostream>
3 #include<cmath>
4 #include<algorithm>
5 #include<cstring>
6 #include<cstdlib>
7 #include<cctype>
8 #include<vector>
9 #include<stack>
10 #include<queue>
11 using namespace std;
12 #define enter puts("")
13 #define space putchar(' ')
14 #define Mem(a) memset(a, 0, sizeof(a))
15 typedef long long ll;
16 typedef double db;
17 const int INF = 0x3f3f3f3f;
18 const db eps = 1e-8;
19 const int maxn = 505;
20 inline ll read()
21 {
22 ll ans = 0;
23 char ch = getchar(), last = ' ';
24 while(!isdigit(ch)) {last = ch; ch = getchar();}
25 while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();}
26 if(last == '-') ans = -ans;
27 return ans;
28 }
29 inline void write(ll x)
30 {
31 if(x < 0) x = -x, putchar('-');
32 if(x >= 10) write(x / 10);
33 putchar(x % 10 + '0');
34 }
35
36 int n, a[maxn], t;
37
38 int dp[maxn], len = -1;
39 void DP()
40 {
41 for(int i = 1; i <= n; ++i)
42 {
43 dp[i] = 1;
44 for(int j = 1; j < i; ++j)
45 if(a[j] <= a[i]) dp[i] = max(dp[i], dp[j] + 1);
46 }
47 }
48
49
50 struct Edge
51 {
52 int from, to, cap, flow;
53 };
54 vector<Edge> edges;
55 vector<int> G[maxn << 1];
56 void addEdge(int from, int to, int w)
57 {
58 edges.push_back((Edge){from, to ,w, 0});
59 edges.push_back((Edge){to, from, 0, 0});
60 int sz = edges.size();
61 G[from].push_back(sz - 2);
62 G[to].push_back(sz - 1);
63 }
64 void init()
65 {
66 edges.clear();
67 for(int i = 0; i < (maxn << 1); ++i) G[i].clear();
68 }
69
70 int dis[maxn << 1];
71 bool bfs()
72 {
73 Mem(dis); dis[0] = 1;
74 queue<int> q; q.push(0);
75 while(!q.empty())
76 {
77 int now = q.front(); q.pop();
78 for(int i = 0; i < (int)G[now].size(); ++i)
79 {
80 Edge& e = edges[G[now][i]];
81 if(!dis[e.to] && e.cap > e.flow)
82 {
83 dis[e.to] = dis[now] + 1;
84 q.push(e.to);
85 }
86 }
87 }
88 return dis[t];
89 }
90 int cur[maxn << 1];
91 int dfs(int now, int res)
92 {
93 if(now == t || res == 0) return res;
94 int flow = 0, f;
95 for(int& i = cur[now]; i < (int)G[now].size(); ++i)
96 {
97 Edge& e = edges[G[now][i]];
98 if(dis[e.to] == dis[now] + 1 && (f = dfs(e.to, min(res, e.cap - e.flow))) > 0)
99 {
100 e.flow += f;
101 edges[G[now][i] ^ 1].flow -= f;
102 flow += f;
103 res -= f;
104 if(res == 0) break;
105 }
106 }
107 return flow;
108 }
109
110 int maxflow()
111 {
112 int flow = 0;
113 while(bfs())
114 {
115 Mem(cur);
116 flow += dfs(0, INF);
117 }
118 return flow;
119 }
120
121 int main()
122 {
123 n = read();
124 t = n + n + 1;
125 for(int i = 1; i <= n; ++i) a[i] = read();
126 DP();
127 for(int i = 1; i <= n; ++i) len = max(len, dp[i]);
128 write(len); enter;
129 for(int i = 1; i <= n; ++i)
130 {
131 addEdge(i, i + n, 1);
132 if(dp[i] == 1) addEdge(0, i, 1);
133 if(dp[i] == len) addEdge(i + n, t, 1);
134 }
135 for(int i = 1; i <= n; ++i)
136 for(int j = i + 1; j <= n; ++j)
137 if(a[j] >= a[i] && dp[j] == dp[i] + 1) addEdge(i + n, j, 1);
138 int ans = maxflow();
139 write(ans); enter;
140 addEdge(0, 1, INF); addEdge(1, 1 + n, INF);
141 addEdge(n, n + n, INF);
142 if(dp[n] == len) addEdge(n, t, INF);
143 write(ans + maxflow()); enter;
144 return 0;
145 }
View Code