[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;
}