P2300 合并神犇

    • 297通过
    • 758提交
  • 题目提供者 千反田爱瑠
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 贪心
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    loidc来到了NOI的赛场上,他在那里看到了好多神犇。

    题目描述

    神犇们现在正排成一排在刷题。每个神犇都有一个能力值p[i]。loidc认为坐在附近的金牌爷能力参差不齐非常难受。于是loidc便想方设法对神犇们进行人道主义合并。

    loidc想把神犇的能力值排列成从左到右单调不减。他每次可以选择一个神犇,把他合并到两侧相邻的神犇上。合并后的新神犇能力值是以前两位犇的能力值之和。每次合并完成后,被合并的两个神犇就会消失。合并后的新神犇不能再分开(万一他俩有女朋友咋办)因此每次合并后神犇的总数会减1.

    loidc想知道,想治好他的强迫症需要合并多少次

    输入输出格式

    输入格式:

    第一行一个整数 n。

    第二行 n 个整数,第 i 个整数表示 p[i]。

    输出格式:

    loidc需要合并的次数

    输入输出样例

    输入样例#1: 复制
    8
    1 9 9 4 1 2 2 9
    输出样例#1: 复制
    3

    说明

    对于 50%的数据,0< n <=5000。

    对于 100%的数据,0< n <=200000,0< p[i] <=2147483647,p 均为随机生成。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。