首页 > 试题广场 >

回文数组

[编程题]回文数组
  • 热度指数：6253 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
对于一个给定的正整数组成的数组 a[] ，如果将 a 倒序后数字的排列与 a 完全相同，我们称这个数组为“回文”的。
例如， [1, 2, 3, 2, 1] 的倒序是他自己，所以是一个回文的数组；而 [1, 2, 3, 1, 2] 的倒序是 [2, 1, 3, 2, 1] ，所以不是一个回文的数组。
对于任意一个正整数数组，如果我们向其中某些特定的位置插入一些正整数，那么我们总是能构造出一个回文的数组。

输入一个正整数组成的数组，要求你插入一些数字，使其变为回文的数组，且数组中所有数字的和尽可能小。输出这个插入后数组中元素的和。

例如，对于数组 [1, 2, 3, 1, 2] 我们可以插入两个 1 将其变为回文的数组 [1, 2, 1, 3, 1, 2, 1] ，这种变换方式数组的总和最小，为 11 ，所以输出为 11 。

输入描述:
输入数据由两行组成： 第一行包含一个正整数 L ，表示数组 a 的长度。 第二行包含 L 个正整数，表示数组 a 。  对于 40% 的数据： 1 < L <= 100 达成条件时需要插入的数字数量不多于 2 个。  对于 100% 的数据： 1 < L <= 1,000 0 < a[i] <= 1,000,000 达成条件时需要插入的数字数量没有限制。


输出描述:
输出一个整数，表示通过插入若干个正整数使数组 a 回文后，数组 a 的数字和的最小值。
示例1

输入

8
51 23 52 97 97 76 23 51

输出

598
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

C++工程师 iOS工程师 动态规划 安卓工程师 数组 运维工程师 前端工程师 搜狐 算法工程师 2018 PHP工程师 Java工程师
上传者：小小
难度：
0条回答 10418浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号