hdu 3998(最长上升子序列及个数）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3998

思路：可以用n*log(n)的做法求出最长上升子序列，然后删除原数组中的这些数，再求最长上升子序列（如果长度减小，则直接退出）。

View Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 #define MAXN 22222
 8 #define inf 1<<30
 9 int dp[MAXN];
10 int num[MAXN];
11 bool mark[MAXN];
12 int n,len,maxlen,_count;
13 
14 int Search(int low,int high,int number){
15     while(low<=high){
16         int mid=(low+high)>>1;
17         if(dp[mid]==number)return mid;
18         else if(dp[mid]>number)high=mid-1;
19         else low=mid+1;
20     }
21     return low;
22 }
23 
24 int main(){
25     while(~scanf("%d",&n)){
26         for(int i=0;i<n;i++){
27             scanf("%d",&num[i]);
28         }
29         maxlen=-inf;
30         memset(mark,false,sizeof(mark));
31         while(1){
32             memset(dp,0,sizeof(dp));
33             dp[0]=-inf,len=0;
34             for(int i=0;i<n;i++){
35                 if(mark[i])continue;
36                 int pos=Search(0,len,num[i]);
37                 dp[pos]=num[i];
38                 if(pos>len){
39                     len++;
40                     mark[i]=true;
41                 }
42             }
43             if(len>maxlen){maxlen=len;_count=1;}
44             else if(len==maxlen)_count++;
45             else break;
46         }
47         printf("%d\n%d\n",maxlen,_count);
48     }
49     return 0;
50 }
51 
52 
53

ps:当然此题也可以用dp+最大流来求，首先求出最长上升子序列的长度，然后就是建图了，可以选择源点为0，由于数列中的每一个数只能使用一次，构图的时候需要拆点。若有n个数，则拆成2 * n个点，构造源点和汇点，将每个点都和自己拆出来的点连边，将源点和最长序列为1的点连边，将最长序列为ans的点与汇点连边，最后若dp[j] = dp[i] + 1,则将i + n和 j连边。所有边的流量都是1，这样便可以限制每个点只使用一次。其实连边的顺序就是最长序列为1，2，3，...，ans。可以理解为从最长序列为1（该数本身）一直流到数列中的最长上升序列。