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

问题的题面是典型的最长上升子序列问题。求方案数属动态规划问题,可推出以a[i]为最大节点的上升子序列方案数公式     dp[i]=\sum{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;
}

相关推荐

  1. 机器学习算法一二三面面经

    2024-07-20 23:04:04       35 阅读
  2. 美团20240420七场笔试【硬件开发方向

    2024-07-20 23:04:04       41 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-20 23:04:04       106 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-20 23:04:04       116 阅读
  3. 在Django里面运行非项目文件

    2024-07-20 23:04:04       95 阅读
  4. Python语言-面向对象

    2024-07-20 23:04:04       103 阅读

热门阅读

  1. ubuntu22.04下YOLOv5 TensorRT模型部署

    2024-07-20 23:04:04       28 阅读
  2. 前端面试题日常练-day98 【Less】

    2024-07-20 23:04:04       30 阅读
  3. Uboot下的命令与环境变量

    2024-07-20 23:04:04       29 阅读
  4. 力扣第二十二题——括号生成

    2024-07-20 23:04:04       27 阅读
  5. WebKit简介及工作流程

    2024-07-20 23:04:04       23 阅读