題目描述

?問題描述：

給定正整數(shù)序列x1,...,xn 。

（1）計算其最長不下降子序列的長度s。

（2）計算從給定的序列中最多可取出多少個長度為s的不下降子序列。

（3）如果允許在取出的序列中多次使用x1和xn，則從給定序列中最多可取出多少個長度為s的不下降子序列。

?編程任務(wù)：

設(shè)計有效算法完成（1）（2）（3）提出的計算任務(wù)。

輸入格式

第1 行有1個正整數(shù)n，表示給定序列的長度。接下來的1 行有n個正整數(shù)n:x1, ..., xn。

輸出格式

第1 行是最長不下降子序列的長度s。第2行是可取出的長度為s 的不下降子序列個數(shù)。第3行是允許在取出的序列中多次使用x1和xn時可取出的長度為s 的不下降子序列個數(shù)。

輸入輸出樣例

輸入 #1 4 3 6 2 5 輸出 #1 2 2 3

說明/提示

n≤500

?

---

【解題思路】

? 運(yùn)用最小割解決問題的本質(zhì)是

? 找到多個問題同時存在且矛盾的情況，利用網(wǎng)絡(luò)流找到最優(yōu)的解

? 于是這個問題的解決方式就能夠這樣解決

? 首先，拆點(diǎn)，一個入點(diǎn)一個出點(diǎn)，考慮他們的連接過程

? 因?yàn)樵搭^流量為 1 ，于是就能夠形成單一的鏈，保證情況獨(dú)立，能夠排除矛盾情況

? 開頭的是長度為 1 的，因?yàn)樽铋L的能夠包括所有子串，所以連接至匯點(diǎn)

? 然后對每個符合要求，對這道題來說就是

? 能夠順利組成增加一個字符串，使這個子串增長

? 如果選擇了這個子串之后，就能夠或者這個子串相應(yīng)的流量

? 在最大流的性質(zhì)和思想下最終也就能夠得到最終答案了

??

---

【代碼】

?

#include<cstdio> #include<queue> #include<cstring> #define ll int using namespace std; const int MAXN = 5010; const int MAXM = 200010; const ll INF = (1ll << 31) - 1; struct note {int to;int nt;int rev;ll cal; }; struct edge {note arr[MAXM];int siz;int maxn;int a[MAXN];int dp[MAXN];int st[MAXN];int dis[MAXN];int cur[MAXN];int depth[MAXN];int top;int n, m, s, t;edge(){memset(st, -1, sizeof(st));memset(depth, -1, sizeof(depth));memset(dis, -1, sizeof(dis));top = 0;}void read(){scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);}int LIS(){for (int i = 1; i <= n; i++)dp[i] = 1;for (int i = 1; i <= n; i++)for (int j = 1; j < i; j++){if (a[j] <= a[i]){dp[i] = max(dp[i], dp[j] + 1);}}maxn = -1;for (int i = 1; i <= n; i++)if (maxn < dp[i])maxn = dp[i];return maxn;}void build(){t = 2*n+2;for (int i = 1; i <= n; i++){add(i, i + n, 1);if(dp[i]==1)add(0, i, 1);if (dp[i] == maxn)add(i + n, t, 1);}for (int i = 1; i <= n; i++)for (int j = 1; j <i; j++)if (a[j] <= a[i] && dp[j] + 1 == dp[i])add(j+n, i , 1);s = 0;siz = 2 * n+1;}bool dep(){queue<int> q;q.push(s);memset(depth, -1, sizeof(depth));depth[s] = 0;while (!q.empty()){int v = q.front(); q.pop();for (int i = st[v]; i != -1; i = arr[i].nt){int to = arr[i].to;if (!arr[i].cal)continue;if (depth[to] != -1)continue;depth[to] = depth[v] + 1;q.push(to);}}return (depth[t] != -1);}void add(int x, int y, ll z){top++; arr[top] = { y,st[x],top + 1,z }; st[x] = top;top++; arr[top] = { x,st[y],top - 1,0 }; st[y] = top;}ll dfs(int now, ll val){if (now == t || !val)return val;ll flow = 0;for (int& i = cur[now]; i != -1; i = arr[i].nt){int to = arr[i].to;if (depth[to] != depth[now] + 1)continue;ll f = dfs(to, min(arr[i].cal, val));if (!f || !arr[i].cal)continue;flow += f;arr[i].cal -= f;arr[arr[i].rev].cal += f;val -= f;if (!val)return flow;}return flow;}ll dinic(){ll flow = 0;ll f;while (dep()){for (int i = 0; i <= siz; i++)cur[i] = st[i];while (f = dfs(s, INF))flow += f;}return flow;} }; edge road,tmp; int main() {road.read();//printf("**\n");printf("%d\n",road.LIS());//printf("**\n");//printf("\n"); road.build();//printf("**\n");tmp = road;printf("%d\n", tmp.dinic());if(road.dp[1]==1)road.add(road.s, 1, INF);if(road.dp[road.n]==road.maxn)road.add(road.n * 2, road.t, INF);road.add(1, road.n + 1, INF);road.add(road.n, road.n * 2, INF);printf("%d", road.dinic());return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/rentu/p/11323873.html

總結(jié)

以上是生活随笔為你收集整理的【P2766】 最长不下降子序列问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。