poj 1952 BUY LOW, BUY LOWER[最长单调子序列变形]

题目：poj 1952 BUY LOW, BUY LOWER 题意：给出一个序列，先求最长单调递减子序列，然后求在子序列最长的情况下，不同的长度都为最长的的子序列的个数。（比如3，2，，1和3，2，1属于相同，只能算一个）

分析：首先用一个dp【i】表示到当前i点的最长子序列的长度 用dp2【i】表示最长为dp【i】的子序列的个数 然后dp【i】 = max（dp【j】）+1 （1<=j

/************************************Problem: 1952User: y990041769Memory: 440KTime: 94MSLanguage: G++Result: AcceptedSource Code*************************/;const int N = 5500;int a[N];int dp[N],dp2[N];int num[N];int cnt;int Bin_search(int l,int r,int val){while(l<=r){int mid = (l+r)/2;if(num[mid]>val)l = mid+1;elser = mid-1;}return l;}int main(){// freopen(“Input.txt”,”r”,stdin);int n;while(~scanf(“%d”,&n)){for(int i=1; i<=n; i++){scanf(“%d”,&a[i]);dp[i] = dp2[i] = 1;}for(int i=1; i<=n; i++){for(int j=i-1; j>0; j–){if(a[i]<a[j]){if(dp[i]<(dp[j]+1)){dp[i] = dp[j]+1;dp2[i] = dp2[j];}else if(dp[i]==(dp[j]+1))dp2[i]+=dp2[j];}else if(a[i]==a[j]){if(dp[i] == 1)dp2[i] = 0;break;}}}int ma = 0;for(int i=1; i<=n; i++)ma = max(ma,dp[i]);int ans = 0;for(int i=1; i<=n; i++)if(dp[i]==ma)ans += dp2[i];printf(“%d %d\n”,ma,ans);}return 0;}

每一件事与每一个美丽景色，都有可能成为一生中的难忘。