首页 > 系统相关 >分披萨,关键在于吃货可能取左或者取右,利用max(递归调用左边,递归调用右边),相当于暴力获取所有结果取得最大值,由于内存消耗过大,暴力递归结果相同的存在cache[l][r]中

分披萨,关键在于吃货可能取左或者取右,利用max(递归调用左边,递归调用右边),相当于暴力获取所有结果取得最大值,由于内存消耗过大,暴力递归结果相同的存在cache[l][r]中

时间:2025-01-04 14:30:53浏览次数:8  
标签:调用 暴力 递归 int 披萨 吃货 cache pizza


#include<bits/stdc++.h>
using namespace std;
int n;//披萨个数
int pizza[500];//n个披萨大小
long cache[500][500];
int check(int id)
{
    if(id<0)
        id=n-1;//若取走披萨第一块的左边,则循环相当于最后一块
    if(id>=n)
    {
        id=0;//若取走披萨最后一块的右边,则相当于第一块
    }
    return id;
}
long recursive(int l,int r)
{
    //馋嘴先拿

    if(pizza[l]>pizza[r])//馋嘴取左边
    {
        l=check(l-1);//馋嘴取完左边,剩下缺口的披萨左边位置
    }
    else//馋嘴取右边
    {
        r=check(r+1);
    }
    //由于吃货拿左边或者拿右边,递归时候可能会有重复,故二维数组保存l,r。若不为0,则说明之前已经递归过了
    //比如l=1,r=4,吃货第一次拿左边时候递归,l=2,r=4,第二次再拿右边l=2,r=3,等价于第一次先拿右边l=1,r=3,第二次再拿左边l=2,r=3。(递归会存在重复,所以缓存判断一下可跳过一些递归)
    if(cache[l][r]>0)
    {
        return cache[l][r];
    }
    //吃货再拿
    if(l==r)//说明只剩一块了,最后一块也是吃货拿,题目说有奇数块,函数最终执行结束条件
         cache[l][r]=pizza[l];
    else
    {
        //说明还剩多块披萨,吃货可能拿左边,也可能拿右边,两边递归,取最大的可能值。也可以理解为递归暴力所有结果取最大值,相当于递归树里找最大的值
        cache[l][r]=max(recursive(check(l-1),r)+pizza[l],recursive(l,check(r+1))+pizza[r]);
    }
    return cache[l][r];
}
int main()
{

    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>pizza[i];
    }
    long chihuo=0;//吃货得到最大披萨大小
    for(int i=0;i<n;i++)
    {
        //i-1左缺口,i+1右缺口
        chihuo=max(chihuo,recursive(check(i-1),check(i+1))+pizza[i]);//吃货第一次取左边后,第二次可能取左或右,因此会出现重复情况,所以可以使用缓存保存可能的递归情况
    }
    cout<<chihuo<<endl;
    return 0;
}
 

标签:调用,暴力,递归,int,披萨,吃货,cache,pizza
From: https://blog.csdn.net/m0_57195330/article/details/144925886

相关文章

  • 淘宝API调用限制是怎样的?
    淘宝API的调用限制主要包括以下几个方面:1.调用频率限制淘宝API对接口的调用频率有严格的限制,不同接口可能有不同的限制。对于普通的开发者,通常每天对每个接口的调用次数都是有限制的,这个数值在几百到几千次不等,具体取决于接口的性质和需求。如果开发者需要更高的调用频率,可......
  • 【初阶数据结构与算法】排序算法总结篇(每个小节后面有源码)(直接插入、希尔、选择、堆
    文章目录一、直接插入排序二、希尔排序三、直接选择排序四、堆排序五、冒泡排序六、快速排序七、归并排序八、计数排序九、非递归快速排序十、非递归归并排序本篇内容将从稳定性与复杂度等角度分析排序算法,列出它们的特点、优点以及缺点,希望大家有所收获,如果想更加细......
  • 记录一次因为JSON转化错误导致的Feign调用失败
    1、用Feign调用其它微服务的接口失败,因工程定义的GlobalExceptionHandler使得报错信息不明显,接口调用结果如图。日志没有将错误打印出来。2、修改GlobalExceptionHandler,错误日志得以详细地打印出来。3、修改返回字段(Date类型的)结果:Feign调用成功。......
  • 使用库函数 API 和 C 代码中嵌入汇编代码两种方式使用同一个系统调用
    实验四使用库函数API和C代码中嵌入汇编代码两种方式使用同一个系统调用实验内容选择一个系统调用(13号系统调用time除外),系统调用列表参见torvalds/linux。参考视频中的方式使用库函数API和C代码中嵌入汇编代码两种方式使用同一个系统调用实验过程使用库函数API#......
  • Python实现Zip文件的暴力破解
    Python实现Zip文件的暴力破解实验内容我们在网上好不容易下载到一个想要的zip资源却发现这个zip文件是加密的,或者忘掉自己压缩后的密码(一想到就头疼)。这时候我们就会想办法,将里面的内容提取出来。我目前已知的破解zip的方式只有“Knownplaintextattack(已知明文攻击)”......
  • 内核编译与系统调用
    Linux内核编译实验内容下载内核源码:确定内核版本号uname-r在www.kernel.org选择接近的内核版本下载linux-6.6.60.tar.xz将压缩包解压到虚拟机目录中确认系统位数getconfLONG_BIT确认虚拟机保留足够大硬盘空间(20G)df-h编写自定义系统调用函数修改/kernel/sys......
  • Linux模块与系统调用
    模块与系统调用1.编写内核模块代码首先,编写一个简单的“HelloWorld”内核模块文件hello_module.c。#include<linux/init.h>//用于宏__init和__exit#include<linux/module.h>//用于模块编程基本宏#include<linux/kernel.h>//用于printk宏MODULE_LI......
  • Dify 框架连接 PGSQL 数据库与 Sandbox 环境下的 Linux 系统调用权限问题
    Dify框架连接PGSQL数据库与Sandbox环境下的Linux系统调用权限问题背景在使用Dify框架进行开发时,遇到了两个主要的技术挑战:代码节点连接到PGSQL(PostgreSQL)数据库。解决沙盒环境中由于系统调用限制导致的“operationnotpermitted”错误。本文档将详细描述如何解......
  • 函数递归与栈帧的创建与销毁
    目录函数递归函数栈帧的创建与销毁概述 main函数栈帧的创建变量的创建如何传参子函数栈帧的创建函数如何返回值(1)子函数栈帧的销毁函数如何返回值(2)函数递归将复杂的问题层层化为与原问题相似的规模较小的问题。递----递推、归----回归 递推:函数一直......
  • 用仓颉完成编译原理实验-消除左递归和左公共因子,求FIRST集和FOLLOW集
    目录实验目的实验内容实现消去上下文无关文法中所有左递归的算法实现从上下文无关文法中提取左公共因子的算法实现求解上下文无关文法的FIRST集和FOLLOW集的算法设计方案与算法描述设计文法的数据结构实现消去上下文无关文法中所有左递归的算法实现从上下文无关文法中......