最长不下降子序列问题

嘟嘟嘟

 

这道题刚开始尝试自己写网络流,然后改来改去最终就写炸了……然后就看了题解,发现好多篇题解都是由一篇衍生出来的……甚至笔误都是一样。

所以我参照完题解后还是觉得应该自己写一篇最能让人看懂的题解。

 

首先,第一问就是比较简单的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

 

上一篇:Git-flow 工作流


下一篇:视频光流提取《FlowNet: Learning Optical Flow with Convolutional Networks》