欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2018年 搜狐校招笔试题 回文数组

程序员文章站 2022-04-02 18:22:38
...

题目描述

对于一个给定的正整数组成的数组 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

说明

/*
贪心的思想, 找到数组最大和对应的回文子序列
然后添加其余的数使得整个数组构成回文。
那么整个数组的和一定是最小的
此时的答案为 sum-dp[0][n-1]+sum 

dp[i][j] 表示从下标i到j对应的回文子序列的最大和

// 转移方程dp[i][j] = dp[i+1][j-1] + 2*num[i] if num[i]=num[j]
//        else dp[i][j] = max(dp[i+1][j],dp[i][j-1])

*/

#include <iostream>
using namespace std;
const int N = 10010;
int num[N];
int dp[N][N];

int main()
{
    int n,s=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>num[i];
        s+=num[i];
    }
    for(int i=0;i<n;i++) dp[i][i] = num[i];
    for(int j=1;j<n;j++){
        for(int i=0;i<n-j;i++){
            if(num[i]==num[i+j]) dp[i][i+j] = dp[i+1][i+j-1]+2*num[i];
            else dp[i][i+j] = max(dp[i+1][i+j],dp[i][i+j-1]);
        }
    }
    cout<<2*s-dp[0][n-1]<<endl;
    
}