转载请注明出处： http://www.cnblogs.com/fraud/ ——by fraud
Sequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1589 Accepted Submission(s): 587
as x[i1], x[i2],...,x[ik], which satisfies follow conditions:
1) x[i1] < x[i2],...,<x[ik];
2) 1<=i1 < i2,...,<ik<=n
As an excellent program designer, you must know how to find the maximum length of the
increasing sequense, which is defined as s. Now, the next question is how many increasing
subsequence with s-length can you find out from the sequence X.
For example, in one case, if s = 3, and you can find out 2 such subsequence A and B from X.
1) A = a1, a2, a3. B = b1, b2, b3.
2) Each ai or bj(i,j = 1,2,3) can only be chose once at most.
Now, the question is:
1) Find the maximum length of increasing subsequence of X(i.e. s).
2) Find the number of increasing subsequence with s-length under conditions described (i.e. num).
have n numbers.
3 6 2 5
2
题意：
给出一个序列，问LIS的长度以及长度为LIS长度的不相交的上升序列的个数
分析：
n2 求出LIS，同时维护好信息，然后构图。
若dp[i]=1,则由源点向该点连一条容量为1的边，若dp[i]=dp[j]+1，则由j向i连一条容量为1的边，若dp[i]=LIS的长度，则由i向汇点连一条容量为1的边。
注意要拆点。虽然这题数据比较水，不拆点也能过。
//#####################
//Author:fraud
//Blog: http://www.cnblogs.com/fraud/
//#####################
#include <iostream>
#include <sstream>
#include <ios>
#include <iomanip>
#include <functional>
#include <algorithm>
#include <vector>
#include <string>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <cctype>
using namespace std;
#define XINF INT_MAX
#define INF 0x3FFFFFFF
#define MP(X,Y) make_pair(X,Y)
#define PB(X) push_back(X)
#define REP(X,N) for(int X=0;X<N;X++)
#define REP2(X,L,R) for(int X=L;X<=R;X++)
#define DEP(X,R,L) for(int X=R;X>=L;X--)
#define CLR(A,X) memset(A,X,sizeof(A))
#define IT iterator
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<PII> VII;
typedef vector<int> VI;
struct edge{
int to,cap,rev;
edge(int _to,int _cap,int _rev)
{
to=_to;
cap=_cap;
rev=_rev;
}
};
const int MAX_V=;
vector<edge>G[MAX_V];
int iter[MAX_V];
int level[MAX_V];
int tot=;
void add_edge(int from,int to,int cap)
{
G[from].PB(edge(to,cap,G[to].size()));
G[to].PB(edge(from,,G[from].size()-));
}
void bfs(int s,int t)
{
CLR(level,-);
queue<int>q;
level[s]=;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=;i<G[u].size();i++)
{
edge &e=G[u][i];
if(e.cap>&&level[e.to]<)
{
level[e.to]=level[u]+;
q.push(e.to);
}
}
}
}
int dfs(int v,int t,int f)
{
if(v==t)return f;
for(int &i=iter[v];i<G[v].size();i++)
{
edge &e=G[v][i];
if(e.cap>&&level[v]<level[e.to])
{
int d=dfs(e.to,t,min(f,e.cap));
if(d>)
{
e.cap-=d;;
G[e.to][e.rev].cap+=d;
return d;
}
}
}
return ;
}
int Dinic(int s,int t)
{
int flow=;
for(;;)
{
bfs(s,t);
if(level[t]<)return flow;
memset(iter,,sizeof(iter));
int f;
while((f=dfs(s,t,INF))>)
{
flow+=f;
}
}
} int a[MAX_V];
int dp[MAX_V];
int main()
{
ios::sync_with_stdio(false);
int n;
while(scanf("%d",&n)!=EOF){
for(int i=;i<n;i++)
scanf("%d",&a[i]);
int ans=;
CLR(dp,);
for(int i=;i<n;i++){
dp[i]=;
for(int j=;j<i;j++){
if(a[j]<a[i]){
dp[i]=max(dp[i],dp[j]+);
}
}
ans=max(ans,dp[i]);
}
int s=*n,t=*n+;
for(int i=;i<t+;i++)G[i].clear();
for(int i=;i<n;i++)add_edge(i,i+n,);
for(int i=;i<n;i++){
if(dp[i]==)add_edge(s,i,);
if(dp[i]==ans)add_edge(i+n,t,);
for(int j=i+;j<n;j++){
if(dp[j]==dp[i]+&&a[i]<a[j]){
add_edge(i+n,j,);
}
}
}
printf("%d\n",ans);
printf("%d\n",Dinic(s,t)); }
return ;
}
代码君