首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

小美的数组合并(美团20240427年暑期实习笔试真题)

编程知识
2024年09月22日 20:03

题目:小美的数组合并

小美拿到了一个数组,她每次操作可以将两个相邻元素ai合并为一个元素,合并后的元素为原来两个元素之和。小美希望最终数组的最小值不小于k。她想知道有多少种不同的合并结果?

输入描述

第一行输入两个正整数n,k,代表数组大小和数组的最大值。

第二行输入个正整数ai,代表小美拿到的数组。

1<=n,k,ai<=200

输出描述

输出一个整数,代表小美可以得到多少种不同的结果。由于结果可能很大,输出对10^9+7取模的结果。

样例输入

4 4

2 3 4 5

样例输出

4

说明

可能得到的数组有:[5,4,5]、[9,5]、[5,9]、[14]这四种。

题解

记忆化搜索

首先定义:dfs(i,p)表示,从第0到 i-1个数,前面是做完合并操作的。当前从第i个位置的数开始考虑,在这样子的子问题下,有多少种合并方法。并且p表示的是,在前面做完合并的考虑操作之后,第i个数的前一个数是什么(极端情况下第0到i-1个数全合并了,也有可能第i-1个数字没有被合并,保持了原来的样子)。

那么递归的最深处的条件是什么呢?是dfs(n-1,p)吗?其实是dfs(n,p),这个时候表示从第0号元素到第n-1号元素,总共n个数字,都做完合并了,我们要考虑的子问题中的数字个数为0了,那分法就是1,但是这个时候还要看一下我们的p,也就是前面做完合并的考虑操作之后,第n号元素(其实为空因为数组就是从0到n-1)的前一个数是什么,如果这个前一个数字比k小,说明这种分法是不符合要求的,返回0,否则的话是满足要求的,返回1。

那么在dfs的中间层中,对于dfs(i,p),如果p,也就是在第0号元素到第n-1号元素考虑完合并之后,第n号元素(其实为空因为数组就是从0到n-1)的前面的那一个数,比k小,那么说明它如果不和a[i]合并的话是不行的(合并了就一定满足条件吗?交由dfs(i+1,?)去判断吧),那么dfs(i,p)=dfs(i,p+a[i]),而如果p>=k,那么就说明它无论和a[i]合并与否,都是可以的,即dfs(i,p) = dfs(i+1,p+a[i]) + dfs(i+1,p)

最后再在dfs的过程中记忆化一下,把返回值存一下dp数组做一下记忆化搜索。

(代码未经验证,但思路大概是这么个思路)

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

vector<vector<int>> dp;
vector<int> arr;
int n, k;

int dfs(int i, int p) {
    if (i == n) {
        return p >= k ? 1 : 0;
    }
    if (dp[i][p] != -1) {
        return dp[i][p];
    }
    int cnt = 0;
    if (p >= k) {
        cnt += dfs(i + 1, arr[i]);
        cnt %= MOD;
        cnt += dfs(i + 1, p + arr[i]);
        cnt %= MOD;
    } else {
    	cnt += dfs(i + 1, p + arr[i]);
        cnt %= MOD;
    }
    dp[i][p] = cnt;
    return cnt;
}
From:https://www.cnblogs.com/kevin-matrix/p/18425843
本文地址: http://www.shuzixingkong.net/article/2209
0评论
提交 加载更多评论
其他文章 ConcurrentLinkedQueue详解(图文并茂)
前言 ConcurrentLinkedQueue是基于链接节点的无界线程安全队列。此队列按照FIFO(先进先出)原则对元素进行排序。队列的头部是队列中存在时间最长的元素,而队列的尾部则是最近添加的元素。新的元素总是被插入到队列的尾部,而队列的获取操作(例如poll或peek)则是从队列头部开始。 与
ConcurrentLinkedQueue详解(图文并茂) ConcurrentLinkedQueue详解(图文并茂) ConcurrentLinkedQueue详解(图文并茂)
数据结构与算法之间有何关系?
数据结构与算法是计算机科学中的两个重要概念,程序=算法+数据结构。数据结构管理数据,算法解决问题,两者相辅相成。数据类型是连接两者的桥梁,数据结构与算法既紧密相连又各有关注。
数据结构与算法之间有何关系? 数据结构与算法之间有何关系? 数据结构与算法之间有何关系?
Blazor开发框架Known-V2.0.11
Known今天发布了V2.0.11版本,本次版本添加了系统WebApi在线测试,系统菜单样式配置,表格支持用户设置栏位显隐和顺序,系统上下文支持静态组件与后端交互,以及对PgSQL进行了详细的测试,修复了一些BUG,网站支持微信扫码注册登录,文档和交流互动板块也更新了一部分。Known框架的功能和文
Blazor开发框架Known-V2.0.11 Blazor开发框架Known-V2.0.11 Blazor开发框架Known-V2.0.11
"放开那代码让我来!"——Cursor帮你写代码的奇妙之旅
让我们开门见山:编程很酷,但也很折磨人。那些长时间盯着屏幕,debug无休止的日子,只有程序员懂得它的酸爽。而就在这个编程焦虑的世界中,Cursor横空出世,带着一系列魔法功能,如同你手中的一根智能魔杖,让写代码变得像煮速冻面一样简单。 Cursor,一款基于AI的编程助手,号称可以从自然语言生成代
"放开那代码让我来!"——Cursor帮你写代码的奇妙之旅 "放开那代码让我来!"——Cursor帮你写代码的奇妙之旅 "放开那代码让我来!"——Cursor帮你写代码的奇妙之旅
Web刷题之polarctf靶场(2)
1.蜜雪冰城吉警店 点开靶场, 发现题目说点到隐藏奶茶(也就是第九杯)就给flag, 但是明显就只有八杯, 猜测大概率考的是前端代码修改 把id=1修改为id=9, 然后回到页面点击原味奶茶即可弹出flag #flag{7d43cc8863ad0ee649048e562fde53ec} 2.召唤神龙
Web刷题之polarctf靶场(2) Web刷题之polarctf靶场(2) Web刷题之polarctf靶场(2)
控制请求并发数量:p-limit 源码解读
p-limit 是一个控制请求并发数量的库,他的整体代码不多,思路挺好的,很有学习价值; 举例 当我们同时发起多个请求时,一般是这样做的 Promise.all([ requestFn1, requestFn2, requestFn3 ]).then(res =&gt;{}) 或者 requestF
控制请求并发数量:p-limit 源码解读 控制请求并发数量:p-limit 源码解读 控制请求并发数量:p-limit 源码解读
手搓大模型Task01:LLama3模型讲解
前言 主要进行Qwen模型架构进行讲解。 1.Qwen整体介绍 Qwen的整体架构与Llama2类似,如下图所示: tokenizer将文本转为词表里面的数值。 数值经过embedding得到一一对应的向量。 attention_mask是用来看见左边、右边,双向等等来设定。 各类下游任务,Casu
手搓大模型Task01:LLama3模型讲解
基础数据结构之数组
数组 1) 概述 定义 在计算机科学中,数组是由一组元素(值或变量)组成的数据结构,每个元素有至少一个索引或键来标识 In computer science, an array is a data structure consisting of a collection of elements (v
基础数据结构之数组 基础数据结构之数组 基础数据结构之数组