TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5993
  • 题目
  • P5993【原题的欢乐赛】合并石子+
    限制 : 时间限制 : - MS   空间限制 : 262144 KB
    评测说明 : 1s,256MB
    问题描述

    动态规划习题中有很多“合并石子”类型的题目,而这次考试考了一道原题,考场上一片欢呼。

    nodgd面前有$n$堆石子,第$i$堆有$a_i$个。每次操作可以合并相邻两堆,合并后放回原位。这样操作$n-1$次后,所有石子都会被合并到一堆中。

    nodgd规定,如果操作中的第一堆石子是由原来的第$x$到第$y$堆合并得到,第二堆石子是由原来的第$y+1$到第$z$堆合并得到,$1\leq x\leq y\lt z\leq n$,则合并的得分等于序列$\{a_y,a_{y-1},\dots,a_{x+1},a_x\}$和序列$\{a_{y+1},\dots,a_{z-1},a_z\}$的最长公共子序列的长度。

    现在nodgd想知道怎样操作才能使$n-1$次操作的得分总和最大,你只需要算出得分总和的最大值即可。

    输入格式

    第一行一个整数$n$,表示一开始有$n$堆石子。

    第二行$n$个空格间隔的整数$a_1,...,a_n$,表示每堆石子的数量。

    输出格式

    输出一行,一个整数,即得分总和的最大值。

    样例输入 1

    5
    1 2 2 1 1

    样例输出 1

    3

    样例输入 2

    10
    3 4 5 4 2 6 2 6 5 3

    样例输出 2

    5

    样例输入 3

    10
    1 2 1 1 1 2 2 1 2 1

    样例输出 3

    11

    样例输入 4

    10
    1 1 1 1 1 1 1 1 1 1

    样例输出 4

    15

    提示

    样例说明1
    · 一开始是{1},{2},{2},{1},{1};
    · 分别合并第1,2堆、第3,4堆,变成{1,2},{2,1},{1},这两次合并得分都是0;
    · 合并此时的前两堆,变成{1,2,2,1},{1},这次合并得分为2;
    · 合并此时的两堆,变成{1,2,2,1,1},这次合并得分为1。
    · 这个方案得分总和为3。可以验证不存在得分更高的合并方案。

    样例说明2
    一种最优的合并顺序如下:
    · {3},{4},{5},{4},{2},{6},{2},{6},{5},{3}
    · {3,4},{5},{4},{2},{6},{2},{6},{5},{3},得分+=0
    · {3,4,5},{4},{2},{6},{2},{6},{5},{3},得分+=1
    · {3,4,5,4},{2},{6},{2},{6},{5},{3},得分+=0
    · {3,4,5,4,2},{6},{2},{6},{5},{3},得分+=0
    · {3,4,5,4,2,6},{2},{6},{5},{3},得分+=0
    · {3,4,5,4,2,6,2},{6},{5},{3},得分+=1
    · {3,4,5,4,2,6,2,6},{5},{3},得分+=1
    · {3,4,5,4,2,6,2,6,5},{3},得分+=1
    · {3,4,5,4,2,6,2,6,5,3},得分+=1

    样例说明3
    一种最优的合并顺序如下:
    · {1},{2},{1},{1},{1},{2},{2},{1},{2},{1}
    · {1},{2},{1},{1},{1},{2},{2},{1},{2,1},得分+=0
    · {1},{2},{1},{1},{1},{2},{2},{1,2,1},得分+=1
    · {1},{2},{1},{1},{1},{2},{2,1,2,1},得分+=1
    · {1,2},{1},{1},{1},{2},{2,1,2,1},得分+=0
    · {1,2,1},{1},{1},{2},{2,1,2,1},得分+=1
    · {1,2,1},{1,1},{2},{2,1,2,1},得分+=1
    · {1,2,1,1,1},{2},{2,1,2,1},得分+=2
    · {1,2,1,1,1,2},{2,1,2,1},得分+=1
    · {1,2,1,1,1,2,2,1,2,1},得分+=4

    数据规模与约定
    对于50%的数据,\(n\leq 30\)
    对于100%的数据,$1\leq n\leq 300,1\leq a_i\leq1000$。


    来源  感谢nodgd