阶梯-度小满春招算法方向第1批

问题的题面是典型的最长上升子序列问题。求方案数属动态规划问题，可推出以a[i]为最大节点的上升子序列方案数公式     dp[i]={dp[j] , 1<=j<=i-1&&f[j]+1==f[i]} （f为最大上升子序列）。

并且这个方案总数不会超过n，因此也无需求余数.......

#include <bits/stdc++.h>
using namespace std;
int n,a[10005],f[10005],dp[10005],maxlen=0,ans=0;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i];
    for(i=1;i<=n;i++)
    {/**< 求最长上升子序列算法 */
        f[i]=1;
        for(j=1;j<i;j++)
            if(a[j]<a[i])
            f[i]=max(f[i],f[j]+1);
        maxlen=max(maxlen,f[i]);/**< 求最长上升子序列的最大长度 */
    }
    for(i=1;i<=n;i++)
    {/**< 求a[i]为最大元素的上升子序列方案数 */
        for(j=1;j<i;j++)
            if(a[j]<a[i]&&f[i]==f[j]+1)
            dp[i]+=dp[j];
        dp[i]=max(dp[i],1);/**< 需要注意，即便没有比a[i]小的a[j]，哪么仍然存在一种方案 */
    }
    for(i=1;i<=n;i++)
        if(f[i]==maxlen)
         ans+=dp[i];
    cout<<ans;
    return 0;
}