首页 > 其他分享 >D. Remove One Element(前缀最大+简单状态机)

D. Remove One Element(前缀最大+简单状态机)

时间:2023-04-25 19:55:26浏览次数:45  
标签:前缀 int Remove 2e5 状态机 Element

题目

题意

  • 输入 n(2≤n≤2e5) 和长为 n 的数组 a(1≤a[i]≤1e9)。
  • 从 a 中去掉一个数(也可以不去掉)。
  • 输出 a 的最长严格递增连续子数组的长度。

思路

  • 一种方法是前缀最长和后缀最长,加起来。这种方法比较简单。
  • 用状态机来写,定义f[i][0/1]分别表示前缀最大到第 i 这个位置上是否用过这唯一一次删除机会
  • \(f[i][0] = a[i] > a[i-1]?f[i-1][0] + 1:1\)
  • \(f[i][1] = max( a[i] > a[i-1]?f[i-1][0] + 1:1,a[i] > a[i-2]?f[i-2][0] + 1:1 )\)
  • 初始状态
    • f[1][0] = f[1][1] = 1;
    • f[2][0] = (a[2] > a[1]) + 1;
    • f[2][1] = 1;

代码

const int N = 2e5 + 10;
int a[N];
int f[N][2];
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n;i ++)
        cin >> a[i];

    f[1][0] = f[1][1] = 1;
    f[2][0] = (a[2] > a[1]) + 1;
    f[2][1] = 1;

    for (int i = 3; i <= n; i++)
    {
        f[i][0] = f[i][1] = 1;
        if(a[i] > a[i - 1])
        {
            f[i][0] = f[i - 1][0] + 1;
            f[i][1] = f[i - 1][1] + 1;
        }

        if (a[i] > a[i - 2])
            f[i][1] = max(f[i][1], f[i - 2][0] + 1);
    }
    int ans = 1;
    for (int i = 1; i <= n;i ++)
        ans = max({ans, f[i][0], f[i][1]});
    cout << ans << endl;
}

标签:前缀,int,Remove,2e5,状态机,Element
From: https://www.cnblogs.com/cfddfc/p/17353663.html

相关文章

  • vue-element-admin报错Error: error:0308010C:digital envelope routines::unsupporte
    安装vue-element-admin报错 nodejs  Node.jsv18.15.0  opensslErrorStack:['error:03000086:digitalenveloperoutines::initializationerror'],library:'digitalenveloperoutines',reason:'unsupported',code:'ERR_OSSL......
  • Element UI 中 el-input 按下回车键会刷新页面的原因及解决方法
    【问题描述】在需求开发的过程中遇到了一个奇怪的问题:点击弹窗开启表单,分明没有添加任何键盘事件,但在按下回车键时会让页面自动刷新,因此影响到了其他功能。 【产生原因】查阅资料后得知,当el-form表单里只有一个 el-input时,按下回车建会自动触发页面提交功能,因此导致了页......
  • vite + vue3 + vue-router4 + ts + element plus + pinia + axios构建项目
    最后是完整的vite.config.ts、main.ts配置1、先用vite创建一个项目npmcreatevite@latest2、安装elementplusyarnaddelement-plus@element-plus/icons-vuevite.config.ts配置组件按需导入,图标自动导入npminstall-Dunplugin-vue-componentsunplugin-auto-impor......
  • vue3中如何引入element-icon并使用
    简单来说,步骤就是:安装——注册——按需引入——使用安装#NPM$npminstall@element-plus/icons-vue#Yarn$yarnadd@element-plus/icons-vue#pnpm$pnpminstall@element-plus/icons-vue注册您需要从@element-plus/icons-vue中导入所有图标并进行全局注册。......
  • element中datetimerange限制时间的选择范围
    <el-date-pickerv-model="Hour"type="datetimerange":picker-options="pickerOptions"range-separator="-"format="yyyy-MM-ddHH"value-format="yyyy-MM-ddHH"start-placehold......
  • Go中的有限状态机FSM的详细介绍
    1、FSM简介1.1有限状态机的定义有限状态机(FiniteStateMachine,FSM)是一种数学模型,用于描述系统在不同状态下的行为和转移条件。状态机有三个组成部分:状态(State)、事件(Event)、动作(Action),事件(转移条件)触发状态的转移和动作的执行。动作的执行不是必须的,可以只转移状态,不指定任何......
  • Vue2和ElementUI编写的无限级菜单路由
    Vue2和ElementUI编写的无限级菜单路由文章转载自:www.javaman.cn<template><div><el-menu:default-active="$route.path"class="el-menu-vertical-demo":collapse="isCollapse"router><templatev-for="item......
  • ElementUI: Uncaught (in promise) cancel 报错
    场景:使用element confirm组件时,点击【取消】按钮,提示错误 Uncaught(inpromise)cancel 代码如下:open(){this.$confirm('此操作将永久删除该文件,是否继续?','提示',{confirmButtonText:'确定',cancelButtonText:'取消',......
  • Element 级联选择器(Cascader)点击文字(或者一行)选中样式回显
    预览图实现的效果1、选中最后一级,下拉框收缩2、下拉框的每一行点击都可以选中3、点击radio,也能实现选中最后一级,下拉框收缩组件代码<el-cascaderref="cascaderHandleRef"v-model="languageIds"class="width-260":options="languageList":props="{check......
  • Element-ui的el-table更新表格局部数据状态
    需求:渲染了一个表格,其中一列的数据较多,超过5条添加展开收起重点:table一定要设置key值。否则更新不生效。 ......