P1934 封印

    • 115通过
    • 387提交
  • 题目提供者 lyx613
  • 评测方式 云端评测
  • 标签 前缀和 动态规划,动规,dp
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    很久以前,魔界大旱,水井全部干涸,温度也越来越高。为了拯救居民,夜叉族国王龙溟希望能打破神魔之井,进入人界“窃取”水灵珠,以修复大地水脉。可是六界之间皆有封印,神魔之井的封印由蜀山控制,并施有封印。龙溟作为魔界王族,习有穿行之术,可任意穿行至任何留有空隙的位置。然而封印不留有任何空隙! 龙溟无奈之下只能强行破除封印。破除封印必然消耗一定的元气。为了寻找水灵珠,龙溟必须减少体力消耗。他可以在破除封印的同时使用越行术。

    神魔之井的封印共有 n 层,每层封印都有一个坚固值。身为魔族的龙溟单独打破一层封印时需要消耗的元气为该层封印的坚固值和封印总层数 n 的平方的乘积; 但他运用越行术时,打破第 i 层到第 j 层封印(i<j)的总元气消耗为第 i, j 层封印的坚固值之和与第 i, j 层之间所有封印层(包括第 i, j 层)的坚固值之和的乘积。同时,为了不惊动蜀山,第 i, j 层封印的坚固值之和必须不大于一个固定值 t(单独打破时该层坚固值可以大于该值) 。

    输入输出格式

    输入格式:

    第一行包含两个正整数 n 和 t,按序表示封印层数和题中所述的固定值。

    第二行为 n 个正整数a1~an,按序表示第 1 层到第 n 层封印的坚固值。

    输出格式:

    仅一行,包含一个正整数,表示最小消耗元气。

    输入输出样例

    输入样例#1: 复制
    6 10
    8 5 7 9 3 5
    输出样例#1: 复制
    578
    

    说明

    【样例说明】

    先单独打破第一层,再用越行术从第二层直接打破到最后一层。 这样消耗元

    气8 × 6^2+ (5 + 5) × (5 + 7 + 9 + 3 + 5) = 578。

    【数据范围】

    对于 10%的数据,n ≤ 10;

    对于 50%的数据,n ≤ 100;

    对于 70%的数据,n ≤ 500;

    对于 100%的数据,n ≤ 1000,ai(1 ≤ i ≤ n) , t ≤ 20000。

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