hdu 3998 Sequence -最长下升子序列+最大流
hdu 3998 Sequence --最长上升子序列+最大流
/*
题意：给出一个序列，问该序列的最长上升子序列的长度是多少，以及相同长度的，组成元素完全不同的最长上升子序列的个数。
思路：第一问用O(n^2)的dp求解，第二问就是最多不相交路径了。
设最长上升子序列的长度为k，第一问解决后，dp数组中保存的是以这个数结尾的最长上升子序列的长度，于是把每个数拆成两个点i和i’，中间连容量为1的边，表示每个数只能选一次，
dp值为1的与源点连边，dp值为k的与汇点连边，容量均为无穷，
然后枚举所有的i和j（j<i），如满足dp[j]+1==dp[i]且a[j]<a[i]，则从j’向i连一条容量无穷的边，然后求最大流即可。
另外此题由于数据规模较小，可以采用求出最长升序列后，枚举删除最长升序列的做法，如此重复多次，也可求得结果，复杂度O(n^3)。
*/
#include<stdio.h>
#include<string.h>
#define inf 0x7fffffff
int data[100010],dp[100010];
int n,m;
struct edge//边
{
int u,v,f,next,b,c;//边的 前节点 后节点 可用流 下条边的编号 原来边上流的上下界
}e[1000000];
int head[1000000],s,t,yong,ind,sum;
int d[1000000],num[1000000];
int min(int a,int b){return a<b?a:b;}
int pro()
{
int ret=0,i,j,k;
memset(dp,0,sizeof(dp));
dp[0]=1;
for(i=1;i<n;i++)
{
k=-1;
for(j=0;j<i;j++)
{
if(data[j]<data[i]&&(k==-1||dp[k]<dp[j]))
k=j;
}
if(k!=-1)
dp[i]=dp[k]+1;
else dp[i]=1;
if(dp[i]>ret)
ret=dp[i];
}
return ret;//返回值居然写成了dp[n-1] 很长时间没有写代码 生疏了
}
void adde(int u,int v,int f)
{
e[yong].f=f,e[yong].u=u,e[yong].v=v;
e[yong].next=head[u],head[u]=yong++;
e[yong].f=0,e[yong].u=v,e[yong].v=u;
e[yong].next=head[v],head[v]=yong++;
}
void build()
{
int i,j;
yong=0;
memset(head,-1,sizeof(head));
//2n点 0--2n-1 s=2n,t=2n+1;
s=2*n,t=2*n+1;
for(i=0;i<n;i++)
adde(2*i,2*i^1,1);
for(i=0;i<n;i++)
{
if(dp[i]==1)
adde(s,2*i,inf);
if(dp[i]==m)
adde(2*i^1,t,inf);
}
for(i=0;i<n;i++)
{
if(dp[i]<m)
{
for(j=i+1;j<n;j++)
{
if(data[i]<data[j]&&dp[j]==dp[i]+1)
adde(2*i^1,2*j,inf);
}
}
}
}
int sap_gap(int u,int f,int s,int t)
{
if(u==t)
return f;
int i,v,mind=t,last=f,cost;
for(i=head[u];i!=-1;i=e[i].next)
{
v=e[i].v;
int flow=e[i].f;
if(flow>0)
{
if(d[u]==d[v]+1)
{
cost=sap_gap(v,min(last,flow),s,t);
e[i].f-=cost;
e[i^1].f+=cost;
last-=cost;
if(d[s]>=t+1)
return f-last;
if(last==0)
break;
}
if(d[v]<mind)
mind=d[v];
}
}
if(last==f)
{
--num[d[u]];
if(num[d[u]]==0)
d[s]=t+1;
d[u]=mind+1;
++num[d[u]];
}
return f-last;
}
int pro2()
{
build();
int f=0;
memset(d,0,sizeof(d));
memset(num,0,sizeof(num));
for(num[s]=t+1;d[s]<t+1;)
f+=sap_gap(s,inf,s,t);
return f;
}
int main()
{
int i;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
scanf("%d",&data[i]);
m=pro();
printf("%d\n",m);
m=pro2();
printf("%d\n",m);
}
return 0;
}