[DP]poj 1952：BUY LOW, BUY LOWER

大致题意：

    给出一列由n个数字组成的数，求出最长递减子序列的长度，并求出共有多少种最长递减子序列。

 

大致思路：
    第一问很简单，第二问实在看不出来了，查的题解，囧啊，大家不要bs我~~大致过程就是在第一个求最长递增子序列的基础上，对于当前元素是否能够接在其他递减子序列后面再做讨论。要注意两个子序列完全相同的情况，在这里完全相同的子序列只能算一个。

 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=10000;
int num[nMax];
int dp[nMax];
int tim[nMax];
int main(){
    int n,i,j,k;
    while(scanf("%d",&n)!=EOF){
        for(i=1;i<=n;i++){
            scanf("%d",&num[i]);
        }
        for(i=1;i<=n;i++){
            dp[i]=1;
            tim[i]=1;
        }
        for(i=1;i<=n;i++){
            for(j=i-1;j>=1;j--){
                if(num[j]>num[i]){
                    if(dp[j]+1>dp[i]){
                        dp[i]=dp[j]+1;
                        tim[i]=tim[j];
                    }
                    else{
                        if(dp[j]+1==dp[i]){
                            tim[i]+=tim[j];
                        }
                    }
                }
                else{
                    if(num[i]==num[j]){
                        if(dp[i]==1){
                            tim[i]=0;
                        }
                        break;
                    }
                }
            }
        }
        int ans1=-1,ans2=0;
        for(i=1;i<=n;i++){
            if(dp[i]>ans1){
                ans1=dp[i];
            }
        }
        for(i=1;i<=n;i++){
            if(dp[i]==ans1){
                ans2+=tim[i];
            }
        }
        cout<<ans1<<" "<<ans2<<endl;
    }
    return 0;
}