题目参见：http://www.byvoid.com/blog/lpf24-solution/
题意：给定A[1],A[2]…A[N]
Question1：最长上升子序列的长度是多少？
Question2：从这个序列中，最多能取出多少个没有重复使用的元素的上升子序列。其长度=Question1
Question3：同2，但A[1]和A[N]能使用无限次。
分析：
第一问：DP
第二问：
对于f[i]=1的点加一条边(S,i,1)
对于f[i]=len的点加一条边(i,T,1)
对于a[j] 求最大流 第三问： 在第二问的图的基础上加入以下两条边 (S,1,INF) 如果f[n]=len，加这条边(n,T,INF) 求最大流 HINT: 1、len表示第一问的答案。 2、我的程序是从0开始的。。。和分析有点出入
code:
#include
#define N 1000000
using namespace std;
const int INF=0x7FFFFFFF/2;
struct gtp{int x,y,next,c,op;} g[E];
int n,a[500],f[500],e,ls[N],d[N],num[N],cur[N],fa[N],S,T,Flow;
int problem1(){
for (int i=0;i
for (int i=1;i
ans=max(f[i],ans);
}
return ans;
}
void add(int x,int y,int c){
e++;
g[e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e; g[e].c=c; g[e].op=e+1;
e++;
g[e].x=y; g[e].y=x; g[e].next=ls[y]; ls[y]=e; g[e].c=0; g[e].op=e-1;
}
void relabel(int k){
int min=T,i=ls[k];
cur[k]=ls[k];
while (i!=0){
if (g[i].c>0 && d[g[i].y]
}
d[k]=min+1;
}
void change(){
int nf=INF;
for (int i=T;i!=S;i=g[fa[i]].x)
if (g[fa[i]].c
for (int i=T;i!=S;i=g[fa[i]].x){
g[fa[i]].c-=nf;
g[g[fa[i]].op].c+=nf;
}
}
void sap(){
Flow=0;
for (int i=0;i<=T;i++){
d[i]=0;
num[i]=0;
cur[i]=ls[i];
}
num[0]=T+1;
int i=S;
while (d[S]<=T){
while (cur[i]!=0){
if (g[cur[i]].c>0 && d[g[cur[i]].y]+1==d[i]) break;
cur[i]=g[cur[i]].next;
}
if (cur[i]==0){
num[d[i]]–;
if (num[d[i]]==0) break;
relabel(i);
num[d[i]]++;
if (i!=S) i=g[fa[i]].x;
}
else{
fa[g[cur[i]].y]=cur[i];
i=g[cur[i]].y;
if (i==T){
change();
i=S;
}
}
}
}
void problem2(int len){
memset(ls,0,sizeof(ls));
S=n;
T=n+1;
e=0;
for (int i=0;i
if (f[i]==len) add(i,T,1);
}
for (int i=0;i
cout << Flow << endl;
}
void problem3(int len){
memset(ls,0,sizeof(ls));
S=n;
T=n+1;
e=0;
add(S,0,INF);
if (f[n-1]==len) add(n-1,T,INF);
for (int i=0;i
if (f[i]==len) add(i,T,1);
}
for (int i=0;i
cout << Flow << endl;
}
int main(){
freopen("alis.in","r",stdin);
freopen("alis.ans","w",stdout);
scanf("%d",&n);
for (int i=0;i
cout << len << endl;
problem2(len);
problem3(len);
return 0;
}