通俗的，对于每个数只能取一次和取无限次，将点拆开加入边约束
因为让求最长上升子序列的个数，所以当一个数字被选择时，它必须是最长上升子序列的一部分
我们求出最长上升子序列的 (DP) 数组，当 (x) 可以连边 (y) 当且仅当 (y) 在 (DP) 中可以从 (x) 转移过来
这样问题就显然了，我们只需要求解 (DAG) 上的最长链个数即可
具体的连边方法，设最长上升子序列长度为 (k)
-
每个 (x) 向 (x') 连边
-
当 (f_x = k) 时，从 (S) 向 (x) 连边
-
当 (x < y) 且 (f_x + 1 = f_y) 且 (v_x < v_y) 时， (y') 向 (x) 连边
-
当 (f_x = 1时，)x'$ 向 (T) 连边
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#include<cctype>
#include<cstring>
using namespace std;
namespace OI{
#define rg register
template <typename T>
inline void read(T &x){
x=0;
static char ch;ch=getchar();
static int f;f=0;
while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=f?-x:x;
}
template <typename T>
inline int min(const T &a,const T &b){ return a<b?a:b; }
template <typename T>
inline int max(const T &a,const T &b){ return a>b?a:b; }
const int N=1005,M=4005;
int head[N],ver[M],nxt[M],flow[M],tot=1;
inline void add(int &x,int &y,int z){
ver[++tot]=y;
flow[tot]=z;
nxt[tot]=head[x];
head[x]=tot;
}
inline void adds(int x,int y,int z){
add(x,y,z);
add(y,x,0);
}
int n,s,t;
int dis[N],cur[N];
int g[505];
inline int bfs(){
queue<int> q;
memset(dis,0,sizeof dis);
dis[s]=1;
q.push(s);
while(!q.empty()){
int x=q.front();q.pop();
cur[x]=head[x];
for(int y,i=head[x];i;i=nxt[i]){
y=ver[i];
if(!dis[y]&&flow[i]){
dis[y]=dis[x]+1;
q.push(y);
}
}
}
return dis[t];
}
int dfs(int x,int f){
if(x==t) return f;
int used=0;
for(int w,y,&i=cur[x];i;i=nxt[i]){
y=ver[i];
if(dis[y]==dis[x]+1&&flow[i]){
w=dfs(y,min(f-used,flow[i]));
if(w){
flow[i]-=w;
flow[i^1]+=w;
used+=w;
if(used==f) return f;
}
}
}
if(!used) dis[x]=0;
return used;
}
inline int dinic(){
int ans=0;
while(bfs()) ans+=dfs(s,0x3f3f3f3f);
return ans;
}
const int top=500;
template <typename T>
inline void ckmax(T &a,const T &b){
if(a<b) a=b;
}
inline void modify(int x,int d){
for(int i=x;i<=n;i+=(i&-i)) ckmax(g[i],d);
}
inline int ask(int x){
int res=0;
for(int i=x;i;i^=(i&-i)) ckmax(res,g[i]);
return res;
}
int a[N],b[N],f[N];
inline void main(){
read(n);
s=0;t=n<<1|1;
for(int i=1;i<=n;++i) read(a[i]),b[i]=a[i];
sort(b+1,b+1+n);
b[0]=unique(b+1,b+1+n)-b-1;
int res=0;
for(int i=1;i<=n;++i){
a[i]=lower_bound(b+1,b+1+b[0],a[i])-b;
f[i]=ask(a[i])+1;
ckmax(res,f[i]);
modify(a[i],f[i]);
}
printf("%d
",res);
for(int i=1;i<=n;++i){
if(f[i]==res){
adds(s,(i<<1)-1,1);
}
if(f[i]==1){
adds(i<<1,t,1);
}
adds((i<<1)-1,i<<1,1);
}
for(int i=1;i<=n;++i){
for(int j=1;j<i;++j){
if(a[i]>=a[j]&&f[i]==f[j]+1){
adds(i<<1,(j<<1)-1,1);
}
}
}
printf("%d
",dinic());
for(int i=2;i<=tot;i=-~-~i){
flow[i]+=flow[i^1];
flow[i^1]=0;
}
adds(1,2,0x3f3f3f3f);
adds((n<<1)-1,n<<1,0x3f3f3f3f);
adds(2,t,0x3f3f3f3f);
if(f[n]==res) adds(s,(n<<1)-1,0x3f3f3f3f);
printf("%d
",dinic());
}
}
signed main(){ OI::main(); return 0; }