我看別人都是用網絡流做的，我不會網絡流。
我的方法是正常的求出最大上升子序列，然後對這個序列中所有的值全部做一下標記，標記這個數據已經使用過。然後對剩下的數據繼續進行求最大上升子序列的操作。直到求出的序列長度達不到最大長度。
這樣能AC是建立在hdu的測試數據比較弱和數據量比較小的情況下，在最惡劣的狀況下，這樣算的時間復雜度是O(n^3)。
還是不習慣用codeblocks debug。
[cpp]
#include<stdio.h>
#include<string.h>
#define N 500
struct node
{
int x,pre;
int count;
} a[N];
int mark[N];
int main()
{
int n;
int i,j,ans;
int count;
while(scanf("%d",&n)!=EOF)
{
for(i=0; i<n; i++)
{
scanf("%d",&a[i].x);
a[i].pre=i;
a[i].count=1;
mark[i]=0;
}
for(i=0; i<n; i++)
{
for(j=0; j<i; j++)
{
if(a[j].x<a[i].x&&a[j].count>=a[i].count)
{
a[i].count=a[j].count+1;
a[i].pre=j;
}
}
}
ans=0;
int temp;
for(i=0; i<n; i++)
{
if(ans<a[i].count)
{
ans=a[i].count;
temp=i;
}
}
int x;
x=temp;
while(1)
{
mark[x]=1;
if(a[x].pre==x)
break;
x=a[x].pre;
}
count=1;
int ss;
ss=ans;
while(ans==ss)
{
for(i=0; i<n; i++)
{
a[i].count=1;
a[i].pre=i;
}
for(i=0; i<n; i++)
{
if(mark[i]==1)
continue;
for(j=0; j<i; j++)
{
if(mark[j]==1)
continue;
if(a[j].x<a[i].x&&a[j].count>=a[i].count)
{
a[i].count=a[j].count+1;
a[i].pre=j;
}
}
}
ans=0;
int temp;
for(i=0; i<n; i++)
{
if(mark[i]==1)
continue;
if(ans<a[i].count)
{
ans=a[i].count;
temp=i;
}
}
if(ans==ss)
count++;
int x;
x=temp;
while(1)
{
mark[x]=1;
if(a[x].pre==x)
break;
x=a[x].pre;
}
}
printf("%d\n",ss);
printf("%d\n",count);
}
return 0;
}
#include<stdio.h>
#include<string.h>
#define N 500
struct node
{
int x,pre;
int count;
} a[N];
int mark[N];
int main()
{
int n;
int i,j,ans;
int count;
while(scanf("%d",&n)!=EOF)
{
for(i=0; i<n; i++)
{
scanf("%d",&a[i].x);
a[i].pre=i;
a[i].count=1;
mark[i]=0;
}
for(i=0; i<n; i++)
{
for(j=0; j<i; j++)
{
if(a[j].x<a[i].x&&a[j].count>=a[i].count)
{
a[i].count=a[j].count+1;
a[i].pre=j;
}
}
}
ans=0;
int temp;
for(i=0; i<n; i++)
{
if(ans<a[i].count)
{
ans=a[i].count;
temp=i;
}
}
int x;
x=temp;
while(1)
{
mark[x]=1;
if(a[x].pre==x)
break;
x=a[x].pre;
}
count=1;
int ss;
ss=ans;
while(ans==ss)
{
for(i=0; i<n; i++)
{
a[i].count=1;
a[i].pre=i;
}
for(i=0; i<n; i++)
{
if(mark[i]==1)
continue;
for(j=0; j<i; j++)
{
if(mark[j]==1)
continue;
if(a[j].x<a[i].x&&a[j].count>=a[i].count)
{
a[i].count=a[j].count+1;
a[i].pre=j;
}
}
}
ans=0;
int temp;
for(i=0; i<n; i++)
{
if(mark[i]==1)
continue;
if(ans<a[i].count)
{
ans=a[i].count;
temp=i;
}
}
if(ans==ss)
count++;
int x;
x=temp;
while(1)
{
mark[x]=1;
if(a[x].pre==x)
break;
x=a[x].pre;
}
}
printf("%d\n",ss);
printf("%d\n",count);
}
return 0;
}
