poj 1952 最長不下降子序列加最長串數

#include <iostream>

#include <limits.h>

using namespace std;

#define inf INT_MAX;

int data[5003];

int dp[5003];

int count[5003];

int minNow=0;

void lds(int n){

memset(dp,0,sizeof(dp));

minNow=0;

memset(count,0,sizeof(count));

count[0]=1;

int t;

for(int i=1;i<=n;i++)

{

dp[i]=1;

t=-1;

for(int j=i-1;j>=0;j--)

{

if(data[i] < data[j])

{

if(dp[j]+1==dp[i]&&data[j]!=t)//dp保證前面的子序列是有序的，如果有相同的，由t排除，如果不同的，兩個的dp值肯定不同

{//是以不會出現count加了不應該加的東西,exp:6 7 6 7 6 4

count[i]+=count[j];

t=data[j];//同理，不可能出現data【j】之前相同的元素，是以直接可以指派給下一個

}

else

if(dp[j]+1>dp[i])

{

dp[i]=dp[j]+1;

count[i]=count[j];

t=data[j];

}

}

}

}

int out=0;

for(int i=0;i<n;i++)

out=max(out,dp[i]);

cout<<out<<" ";

cout<<count[n]<<endl;

};

int main()

{

int n;

cin>>n;

{

for(int i=1;i<=n;i++)

scanf("%d",&data[i]);

data[0]=1<<30;

lds(n+1);

}

}