这道题用n方的算法会很好做

我一开始想的是nlogn的算法求方案数，

然后没有什么想法（实际上也可以做，但是我太弱了）

我们就可以根据转移方程来推方案数，只是把max改成加，很多动规题

都是这样，比如背包的方案数。

设f[i]为以i为结尾的方案数

当 b[j] + 1 == b[i] 且 a[j] > a[i]时，f[i] 加上f[j]

同时要去重，当b[i] == b[j] 且 a[i] == a[j]时，f[i]为0

另外int最大范围是2^31-1，按理来说这道题应该开longlong，但是可以ac，

说明数据比较弱。但是以后做其他题还是要注意

总结一波

int范围  -2^31 ~ 2^31-1

unsigned int 0 ~ 2 ^ 32 - 1

long long 范围  -2^63 ~ 2^63-1

unsigned long long 范围 0 ~ 2^64-1

#include
    
     #include
     
      #define REP(i, a, b) for(int i = (a); i < (b); i++)using namespace std;const int MAXN = 5123;int a[MAXN], b[MAXN], f[MAXN], n;bool cmp(int a, int b){    return a > b;}int main(){    scanf("%d", &n);    REP(i, 0, n) scanf("%d", &a[i]);        int ans1 = 0, ans2 = 0;    REP(i, 0, n)    {        b[i] = 1;        REP(j, 0, i)            if(a[i] < a[j])                b[i] = max(b[i], b[j] + 1);        ans1 = max(ans1, b[i]);    }        REP(i, 0, n)    {        if(b[i] == 1) f[i] = 1;        REP(j, 0, i)        {            if(b[j] + 1 == b[i] && a[j] > a[i])                f[i] += f[j];            else if(b[i] == b[j] && a[i] == a[j])                f[i] = 0;        }        if(b[i] == ans1) ans2 += f[i];    }    printf("%d %d\n", ans1, ans2);    return 0;}