View Code of Problem 1037

#include<iostream>
using namespace std;

#define MAX 5050

int f[MAX]; //f[i]表示以第i个元素作为最后一个字符的最长递减子序列的长度
int data[MAX];
int countn[MAX];//表示以第i个元素作为最后一个字符且长度为f[i]的是不同的最长递减子序列的方案数

int main()
{
    int n;
    while (cin>>n && n)
    {
        int i,j;
        int max = 0;

        for (i=1;i<=n;i++)
        {
            cin>>data[i];
            f[i] = 0;
            countn[i] = 0;
        }
        f[0] = 0;

        //求最大递减子序列
        data[0] = 999999999;
        for (i=1;i<=n;i++)
        {
            for (j=i-1;j>=0;j--)
                if (data[j] > data[i] && f[j] + 1 > f[i])
                    f[i] = f[j] + 1;

            if (max < f[i])//将最长的长度保存
                max = f[i];
        }
        //////////////////////////////////////


        //计算数量，也是一个DP，转换方程为
        //countn[i] = all(countn[j])  && dp[i] = dp[j]+1 && data[i]<data[j]
        //还要注意去除掉序列中相同位置且数据相同的元素，我采用的是去除的方法
        int Acount = 0;
        countn[0] = 1;

        for (i=1;i<=n;i++)
        {
            for (j=i-1;j>=0;j--)
            {
                if (f[i] == f[j] && data[i] == data[j]) //位置和数据一致，则不重复计算
                    break;
                if (f[i] == f[j]+1 && data[i] < data[j])
                    countn[i]+=countn[j];
            }
            if (f[i] == max  && countn[i]) //达到了最长子序列的长度
                Acount += countn[i];

        }

        cout<<max<<" "<<Acount<<endl;
    }

    return 0;
}