https://www.luogu.org/problemnew/show/P2766
注：题目描述有误，本题求的是最长不下降子序列
方案无限多时输出 n
网络流求方案数，长见识了
第一问：
DP
同时得到f[i] 表示 以第i个数为开头的最长不下降子序列长度
第二问：
每个点拆出2个点 i<<1,i<<1|1，之间连流量为1的边
如果f[i]==最长长度，源点向i<<1连流量为1的边
如果f[i]==1,i<<1|1向汇点连流量为1的边
如果 i<j && f[i]==f[j]+1 i<<1 向j<<1|1 连流量为1的边
这样每一条增广路就是一个方案
第三问：
源点向1<<1，向n<<1连的边，
1<<1|1，n<<1|1向汇点连的边，
1<<1与1<<1|1，n<<1与n<<1|1 之间的边
流量改为inf
小错误：
特判序列为单调下降序列
因为 源点会向每个1<<1连流量为inf 的边
1<<1|1又会向汇点连inf的边
这样导致第三问跑出负无穷，第9、10 测试点挂了的可能是这个原因
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> using namespace std; #define N 1011
#define M 300001
const int inf=2e9; int n;
int a[]; int max_len;
int f[]; int tot=;
int front[N],to[M<<],nxt[M<<],val[M<<],from[M<<]; int lev[N],num[N];
int path[N];
int cur[N]; int src,decc; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void dp()
{
int mx;
for(int i=n;i;--i)
{
mx=;
for(int j=i+;j<=n;++j)
if(a[j]>=a[i]) mx=max(mx,f[j]);
f[i]=mx+;
max_len=max(max_len,f[i]);
}
cout<<max_len;
} void add(int u,int v,int w)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; val[tot]=w; from[tot]=u;
to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; val[tot]=; from[tot]=v;
// cout<<u<<' '<<v<<' '<<w<<'\n';
} void build()
{
for(int i=;i<=n;++i) add(i<<,i<<|,);
for(int i=;i<=n;++i)
if(f[i]==max_len) add(src,i<<,);
for(int i=;i<=n;++i)
if(f[i]==) add(i<<|,decc,);
for(int i=;i<=n;++i)
for(int j=;j<i;++j)
if(a[j]<=a[i] && f[i]==f[j]-) add(j<<|,i<<,);
} void rebuild()
{
tot=;
memset(front,,sizeof(front)); add(<<,<<|,inf);
add(n<<,n<<|,inf);
for(int i=;i<n;++i) add(i<<,i<<|,); if(f[]==max_len) add(src,<<,inf);
if(f[n]==max_len) add(src,n<<,inf);
for(int i=;i<n;++i)
if(f[i]==max_len) add(src,i<<,); if(f[]==) add(<<|,decc,inf);
if(f[n]==) add(n<<|,decc,inf);
for(int i=;i<n;++i)
if(f[i]==) add(i<<|,decc,); for(int i=;i<=n;++i)
for(int j=;j<i;++j)
if(a[j]<=a[i] && f[i]==f[j]-) add(j<<|,i<<,);
} bool bfs()
{
for(int i=src;i<=decc;++i) lev[i]=decc;
queue<int>q;
q.push(decc);
lev[decc]=;
int now,t;
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=front[now];i;i=nxt[i])
{
t=to[i];
if(lev[t]==decc && val[i^])
{
lev[t]=lev[now]+;
q.push(t);
}
}
}
return lev[src]!=decc;
} int augment()
{
int flow=inf,now=decc;
int i;
while(now!=src)
{
i=path[now];
flow=min(flow,val[i]);
now=from[i];
}
now=decc;
while(now!=src)
{
i=path[now];
val[i]-=flow;
val[i^]+=flow;
now=from[i];
}
return flow;
} void isap()
{
if(!bfs())
{
cout<<'\n'<<;
return;
}
memset(num,,sizeof(num));
for(int i=src;i<=decc;++i) num[lev[i]]++;
int flow=;
int now=src,t;
while(lev[src]<decc)
{
if(now==decc)
{
flow+=augment();
now=src;
}
bool advanced=false;
for(int i=front[now];i;i=nxt[i])
{
t=to[i];
if(lev[t]==lev[now]- && val[i])
{
advanced=true;
path[t]=i;
cur[now]=i;
now=t;
break;
}
}
if(!advanced)
{
int mi=decc;
for(int i=front[now];i;i=nxt[i])
if(val[i]) mi=min(mi,lev[to[i]]);
if(!num[--lev[now]]) break;
num[lev[now]=mi+]++;
cur[now]=front[now];
if(now!=src) now=from[path[now]];
}
}
cout<<'\n'<<flow;
} int main()
{
read(n);
src=; decc=(n<<|)+;
for(int i=;i<=n;++i) read(a[i]);
dp();
if(max_len==)
{
cout<<'\n'<<n<<'\n'<<n;
return ;
}
build();
isap();
rebuild();
isap();
}
题目描述
«问题描述：
给定正整数序列x1,...,xn 。
（1）计算其最长递增子序列的长度s。
（2）计算从给定的序列中最多可取出多少个长度为s的递增子序列。
（3）如果允许在取出的序列中多次使用x1和xn，则从给定序列中最多可取出多少个长度为s的递增子序列。
«编程任务：
设计有效算法完成（1）（2）（3）提出的计算任务。
输入输出格式
输入格式：
第1 行有1个正整数n，表示给定序列的长度。接下来的1 行有n个正整数n:x1, ..., xn。
输出格式：
第1 行是最长递增子序列的长度s。第2行是可取出的长度为s 的递增子序列个数。第3行是允许在取出的序列中多次使用x1和xn时可取出的长度为s 的递增子序列个数。
输入输出样例
说明
n\le 500n≤500