This post is written in Chinese. Please consider using Google Translate

动态规划题，就是最长下降序列问题。第一问可以用O(N^2)的算法解决。

s[i]为序列中第i项的值，MaxLength[i]为以第i项为末尾中最长下降序列长度。

状态转移方程为 MaxLength[i]=max{MaxLength[j]}+1 (j=1..i-1 and s[j]>s[i])

初始条件

MaxLength[1]=1

对于第二问求最长下降序列的数量，可以通过求第一问的过程解决。设MaxCnt[i]为第i项为末尾中最长下降序列的个数。

对于所有的j(1≤j≤i-1)如果有(s[j]>s[i] 并且 MaxLength[j]+1>MaxLength[i])则MaxCnt[i]=MaxCnt[j]，否则如果(MaxLength[j]+1==MaxLength[i])可利用加法原理，MaxCnt[i]=MaxCnt[i]+MaxCnt[j]。

考虑到题目中说的不能又重复的序列，我们可以增加一个域Next[i]表示大于i且离i最近的Next[i]使得第Next[i]个数与第i个数相同。如果不存在这样的数则Next[i]=0。这样我们在DP的时候如果出现Next[i]不为0且Next[j]<i可直接跳过。

这个题数据规模很大，需要用到高精度计算，还好只是加法。 USER: CmYkRgB CmYkRgB [cmykrgb1] TASK: buylow LANG: C++

Compiling... Compile: OK

Executing... Test 1: TEST OK [0.000 secs, 3076 KB] Test 2: TEST OK [0.011 secs, 3076 KB] Test 3: TEST OK [0.000 secs, 3076 KB] Test 4: TEST OK [0.022 secs, 3072 KB] Test 5: TEST OK [0.000 secs, 3076 KB] Test 6: TEST OK [0.011 secs, 3072 KB] Test 7: TEST OK [0.011 secs, 3076 KB] Test 8: TEST OK [0.000 secs, 3076 KB] Test 9: TEST OK [0.054 secs, 3072 KB] Test 10: TEST OK [0.324 secs, 3076 KB]

All tests OK.

Your program ('buylow') produced all correct answers! This is your submission #2 for this problem. Congratulations!

/*
ID: cmykrgb1
PROG: buylow
LANG: C++
*/
#include <iostream>
#include <fstream>
#define MAX 5002
#define MAXP 8
#define LIM 1000000000
using namespace std;


class hpnum
{
public:
    long sec[MAXP];
    int seccnt;

    hpnum()
    {
        sec[seccnt=1]=0;
    }
    void plus(hpnum &P)
    {
        int sect=seccnt>P.seccnt?seccnt:P.seccnt;
        long T,up=0;
        for(int i=1;i<=sect;i++)
        {
            if (i>seccnt)sec[i]=0;
            if (i>P.seccnt)P.sec[i]=0;
            T=sec[i]+P.sec[i]+up;
            up=T/LIM;
            sec[i]=T%LIM;
        }
        seccnt=sect;
        if (up)
            sec[++seccnt]=up;
    }
    void cpy(hpnum &P)
    {
        seccnt=P.seccnt;
        for (int i=1;i<=seccnt;i++)
            sec[i]=P.sec[i];
    }
};

ifstream fi("buylow.in");
ofstream fo("buylow.out");

int N;
long s[MAX],MaxLength[MAX],Next[MAX];
hpnum MaxCnt[MAX];

void init()
{
    int i,j;
    fi >> N;
    for (i=1;i<=N;i++)
        fi >>s[i];
    for (i=1;i<=N-1;i++)
        for (j=i+1;j<=N;j++)
            if (s[j]==s[i])
            {
                Next[i]=j;
                break;
            }
    s[++N]=0;
}

void dynamic()
{
    int i,j;
    MaxLength[1]=1;
    MaxCnt[1].sec[1]=1;
    for (i=2;i<=N;i++)
    {
        MaxCnt[i].sec[1]=1;
        MaxLength[i]=1;
        for (j=1;j<=i-1;j++)
        {
            if (Next[j] && Next[j]<i) continue;
            if (s[j]>s[i])
            {
                if (MaxLength[j]+1>MaxLength[i])
                {
                    MaxLength[i]=MaxLength[j]+1;
                    MaxCnt[i].cpy(MaxCnt[j]);
                }
                else if (MaxLength[j]+1==MaxLength[i])
                {
                    MaxCnt[i].plus(MaxCnt[j]);
                }
            }
        }
    }
}

void writehp(hpnum &P)
{
    int i;
    long k;
    for (i=P.seccnt;i>=1;i--)
    {
        k=LIM/10;
        if (i!=P.seccnt && P.sec[i]<k)
        {
            //补0输出
            while (P.sec[i]<k)
            {
                fo << 0;
                k/=10;
            }
        }
        if (P.sec[i])
            fo << P.sec[i];
    }
}

void print()
{
    fo << MaxLength[N]-1 << ' ';
    writehp(MaxCnt[N]);
    fo << endl;
    fi.close();
    fo.close();
}

int main()
{
    init();
    dynamic();
    print();
    return 0;
}