题目大意：给定正整数序列x1,...,xn 。（1）计算其最长不下降子序列的长度s。（不一定是否连续）（2）计算从给定的序列中最多可取出多少个长度为s的不下降子序列。（序列内每一个元素不可重复）（3）如果允许在取出的序列中多次使用x1和xn，则从给定序列中最多可取出多少个长度为s的不下降子序列。
关键词：不相交路径，拆点
（1）DP经典题LIS。令原序列为A[i]，DP[i]表示以i为结尾的不下降子序列长度最长为多少。
（2）
不相交路径：想象有一个流把一个子序列内的每一个元素都串了起来。后一个元素与前一个元素可连接的标志是DP[j]=DP[i]+1且A[i]<=A[j]。
拆点：每个元素只能访问一次，因此把一个元素拆成一条容量为1的边，两元素若可连接，则将前元素的to点连后元素的from点。为了从头开始，从尾结束，因此将S与DP[i]=1的元素边的from点连，DP[i]=S的元素边的to点与T连。然后求最大流即可。
（3）将与1元素边的from点和与n元素边的to节点相连的正向边容量设为∞，然后求最大流。
#include <cstdio> #include <cstring> #include <cassert> #include <queue> #include <algorithm> #include <cmath> using namespace std; #define LOOP(i,n) for(int i=1; i<=n; i++) const int MAX_NODE = 1010, MAX_EDGE = MAX_NODE*MAX_NODE, INF = 0x3f3f3f3f;//注意MAX_NODE=500*2 int A[MAX_NODE], DP[MAX_NODE]; int Tot, MaxLen, Sid, Tid; //#define test struct Dinic { struct Edge; struct Node; struct Node { int Id, Level; Edge* Head; Edge *DfsFrom; }; struct Edge { int Cap, OrgCap; Node *From, *To; Edge *Next, *Rev; Edge(int cap, Node *from, Node *to, Edge *next) :Cap(cap), OrgCap(cap), From(from), To(to), Next(next) {} }; Node _nodes[MAX_NODE]; Edge *_edges[MAX_EDGE]; int _vCount, _eCount; Node *Start, *Target; void Init(int Sid, int Tid, int vCount) { memset(_nodes, 0, sizeof(_nodes)); memset(_edges, 0, sizeof(_edges)); _eCount = 0; Start = Sid + _nodes; Target = Tid + _nodes; _vCount = vCount; } void Recover() { LOOP(i, _eCount) _edges[i]->Cap = _edges[i]->OrgCap; } Edge* AddEdge(Node *from, Node *to, int cap) { Edge *e = _edges[++_eCount] = new Edge(cap, from, to, from->Head); e->From->Head = e; return e; } void Build(int uId, int vId, int eCap) { Node *u = uId + _nodes, *v = vId + _nodes; u->Id = uId; v->Id = vId; Edge *edge1 = AddEdge(u, v, eCap), *edge2 = AddEdge(v, u, 0); edge1->Rev = edge2; edge2->Rev = edge1; } bool Bfs() { for (int i = 1; i <= _vCount; i++) _nodes[i].Level = 0; static queue<Node*> q; Start->Level = 1; q.push(Start); while (!q.empty()) { Node *u = q.front(); q.pop(); for (Edge *e = u->Head; e; e = e->Next) { assert(e->Cap >= 0); if (!e->To->Level && e->Cap) { e->To->Level = u->Level + 1; q.push(e->To); } } } return Target->Level; } int Dfs(Node *cur, int limit) { if (cur == Target) return limit; if (limit == 0) return 0; int curTake = 0; for (Edge *e = cur->DfsFrom; e; cur->DfsFrom = e = e->Next) { if (e->To->Level == cur->Level + 1 && e->Cap) { int nextTake = Dfs(e->To, min(limit - curTake, e->Cap)); e->Cap -= nextTake; e->Rev->Cap += nextTake; curTake += nextTake; } if (limit - curTake == 0) break; } return curTake; } int Proceed() { int ans = 0; while (Bfs()) { for (int i = 0; i <= _vCount; i++) _nodes[i].DfsFrom = _nodes[i].Head; ans += Dfs(Start, INF); } return ans; } }g; void P1() { LOOP(j, Tot) { int maxLen = 0; LOOP(i, j - 1) if (A[i] <= A[j]) maxLen = max(maxLen, DP[i]); DP[j] = maxLen + 1; } MaxLen = 0; LOOP(i, Tot) MaxLen = max(MaxLen, DP[i]); printf("%d ", MaxLen); } void P2() { Sid = Tot * 2 + 1, Tid = Tot * 2 + 2; g.Init(Sid, Tid, Tid); LOOP(i, Tot) g.Build(i, i + Tot, 1); LOOP(i, Tot) { if (DP[i] == 1) g.Build(Sid, i, 1); if (DP[i] == MaxLen) g.Build(i + Tot, Tid, 1); else for (int j = i + 1; j <= Tot; j++) if (DP[j] == DP[i] + 1 && A[j] >= A[i]) g.Build(i + Tot, j, 1); } printf("%d ", g.Proceed()); } void P3() { for (Dinic::Edge* e = g._nodes[1].Head; e; e = e->Next) { if (e->To->Id == 1 + Tot) e->OrgCap = INF; else if (e->To == g.Start) e->Rev->OrgCap = INF; } for (Dinic::Edge *e = g._nodes[Tot * 2].Head; e; e = e->Next) { if (e->To->Id == Tot) e->Rev->OrgCap = INF; else if (e->To == g.Target) e->OrgCap = INF; } g.Recover(); printf("%d ", g.Proceed()); } int main() { #ifdef _DEBUG freopen("c:\noi\source\input.txt", "r", stdin); #endif scanf("%d", &Tot); LOOP(i, Tot) scanf("%d", i + A); P1(); P2(); P3(); return 0; }
注意：
1.本题是“不下降”，而不是“上升”。因此（1）题DP时应该为A[i]<=A[j]，而不是A[i]<A[j]。
2.（2）问不要忘了判断元素可连接的标志还有A[i]<=A[j]。
3.（3）题改容量时注意改的到底时正向边的容量还是反向边的容量，要清楚。