网络流二十四题之六 —— 最长不下降子序列问题（ALIS）

最长不下降子序列问题

---

Description

给定正整数序列 $x_1 ,…, x_n$ 。
（1）计算其最长不下降子序列的长度 $s$。
（2）计算从给定的序列中最多可取出多少个长度为 $s$ 的不下降子序列。
（3）如果允许在取出的序列中多次使用 $x_1$ 和 $x_n$，则从给定序列中最多可取出多少个长
度为 $s$ 的不下降子序列。

---

Input

文件第 $1$ 行有 $1$ 个正整数 $n$，表示给定序列的长度。
接下来的 $1$ 行有 $n$ 个正整数 $x_1 , …, x_n$ 。

---

Output

程序运行结束时，将任务（1）（2）（3）的解答输出。
第 $1$ 行是最长不下降子序列的长度 $s$。
第 $2$ 行是可取出的长度为 $s$ 的不下降子序列个数。
第 $3$ 行是允许在取出的序列中多次使用 $x_1$ 和 $x_n$ 时可取出的长度为 $s$ 的不下降子序列个数。

---

Sample Input

4
3 6 2 5

---

Sample Output

2
2
3

---

Solution

第一问用动态规划。因为数据规模不大，$O(n^2)$ 可以过。

第二问用网络流。
若存在 $j>i$，并且 $f_j = f_i+1$（$f_i$ 表示以 $i$ 为结束的最长不下降子序列的长度），那么将 $i$ 与 $j$ 连一条边。
连接 $i$ 与 $s$，当 $f_i = 1$。
连接 $i$ 与 $t$，当 $f_i = ans_1$。
求最大流即可。

第三问，将第一个点和最后一个点连的边的权值设为 ∞ <script type="math/tex" id="MathJax-Element-1385">∞</script> 即可。

---

Code

[cpp]

1. #include <iostream>  
2. #include <cstdio>  
3. #include <cstring>  
4. #include <queue>  
5.   
6. #define Max(x,y) ((x)>(y)?(x):(y))  
7. #define Min(x,y) ((x)<(y)?(x):(y))  
8. #define ss 0  
9. #define tt 900  
10. #define INF 0x3f3f3f3f  
11.   
12. using namespace std;  
13.   
14. int n,ans1,cnt;  
15. int s[1000];  
16. int f[1000];  
17. int head[1000];  
18. int nxt[1000010];  
19. int data[1000010];  
20. int flow[1000010];  
21. int dis[1000];  
22. queue<int>q;  
23.   
24. void add(int x,int y,int z){  
25.     nxt[cnt]=head[x];data[cnt]=y;flow[cnt]=z;head[x]=cnt++;  
26.     nxt[cnt]=head[y];data[cnt]=x;flow[cnt]=0;head[y]=cnt++;   
27. }  
28.   
29. bool BFS(){  
30.     memset(dis,-1,sizeof dis);  
31.     dis[ss]=0;  
32.     q.push(ss);  
33.     while(!q.empty()){  
34.         int now=q.front();  
35.         q.pop();  
36.         for(int i=head[now];i!=-1;i=nxt[i]){  
37.             if(flow[i]&&dis[data[i]]==-1){  
38.                 q.push(data[i]);  
39.                 dis[data[i]]=dis[now]+1;   
40.             }  
41.         }  
42.     }  
43.     return dis[tt]>0;  
44. }  
45.   
46. int dfs(int now,int low){  
47.     if(now==tt)return low;  
48.     int Low;  
49.     for(int i=head[now];i!=-1;i=nxt[i]){  
50.         if(flow[i]&&dis[data[i]]==dis[now]+1){  
51.             if(Low=dfs(data[i],Min(low,flow[i]))){  
52.                 flow[i]-=Low;  
53.                 flow[i^1]+=Low;  
54.                 return Low;  
55.             }  
56.         }  
57.     }     
58.     return 0;  
59. }  
60.   
61. int main(){  
62.     freopen(”alis.in”,“r”,stdin);  
63.     freopen(”alis.out”,“w”,stdout);  
64.     scanf(”%d”,&n);  
65.     memset(head,-1,sizeof head);  
66.     for(int i=1;i<=n;i++)scanf(“%d”,&s[i]);  
67.     f[1]=1;  
68.     for(int i=2;i<=n;i++){  
69.         f[i]=1;  
70.         for(int j=1;j<i;j++)  
71.             if(s[i]>=s[j])f[i]=Max(f[i],f[j]+1);  
72.         ans1=Max(ans1,f[i]);  
73.     }  
74.     printf(”%d\n”,ans1);  
75.     for(int i=1;i<=n;i++){  
76.         if(f[i]==1)add(ss,i,1);  
77.         if(f[i]==ans1)add(i,tt,1);  
78.         for(int j=i+1;j<=n;j++)  
79.             if(f[j]==f[i]+1&&s[j]>=s[i])add(i,j,1);  
80.     }  
81.     int flag,ans2=0;  
82.     while(BFS())  
83.         while(flag=dfs(ss,INF))ans2+=flag;  
84.     printf(”%d\n”,ans2);  
85.     if(ans1==1){  
86.         printf(”%d\n”,ans2);  
87.         return 0;  
88.     }  
89.     cnt=0;  
90.     memset(head,-1,sizeof head);  
91.     memset(data,0,sizeof data);  
92.     memset(nxt,0,sizeof nxt);  
93.     memset(flow,0,sizeof flow);  
94.     for(int i=1;i<=n;i++){  
95.         if(f[i]==1){  
96.             if(i!=1&&i!=n)  
97.                 add(ss,i,1);  
98.             else add(ss,i,INF);  
99.         }  
100.         if(f[i]==ans1){  
101.             if(i!=1&&i!=n)  
102.                 add(i,tt,1);  
103.             else add(i,tt,INF);  
104.         }  
105.         for(int j=i+1;j<=n;j++)  
106.             if(f[j]==f[i]+1&&s[j]>=s[i]){  
107.                 if(ans1==2&&i==1&&j==n){  
108.                     add(i,j,1);  
109.                     continue;  
110.                 }  
111.                 if(i==1||i==n||j==1||j==n)   
112.                     add(i,j,INF);  
113.                 else add(i,j,1);  
114.             }  
115.     }  
116.     int ans3=0;  
117.     while(BFS())  
118.         while(flag=dfs(ss,INF))ans3+=flag;  
119.     printf(”%d\n”,ans3);  
120.     return 0;  
121. }