[49]回文数组-搜狐2018秋

1.题目描述

对于一个给定的正整数组成的数组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 的数字和的最小值。
• 输入示例

  8
  51 23 52 97 97 76 23 51
  

• 输出示例

  598
  

2.题目解析

动态规划

• 递归

#include <bits/stdc++.h>
using namespace std;
int n = 0;
int solve(int i,int j,int* nums){
  if(i > j) return 0;
  if(i == j) return nums[i];
  if(nums[i] == nums[j]){
    return 2*nums[i]+solve(i+1,j-1,nums);// 首尾两个数相同
  }else{
    return min(2 * nums[i] + solve(i + 1, j,nums), 
               2 * nums[j]+solve(i,j-1,nums));
  }
}
int main() {
  scanf("%d", &n);
  int nums[n];
  for(int i=0;i!=n;++i){
    scanf("%d", &nums[i]);
  }
  printf("%d\n",solve(0,n-1,nums));
}

3.参考答案

• 自顶而下(备忘录)

#include <bits/stdc++.h>
using namespace std;
int n = 0;
int solve(int i,int j,int* nums,vector<vector<int>>& memo){
  if(i > j) return 0;
  if(i == j) return nums[i];
  if(-1 != memo[i][j]) return memo[i][j];
  if(nums[i] == nums[j]){
    memo[i][j] = 2*nums[i]+solve(i+1,j-1,nums,memo);
  }else{
    memo[i][j] = min(2 * nums[i] + solve(i + 1, j,nums,memo),
                     2 * nums[j] + solve(i,j-1,nums,memo));
  }
  return memo[i][j];
}
int main() {
  scanf("%d", &n);
  int nums[n];
  vector<vector<int>> memo(n,vector<int>(n,-1));
  for(int i=0;i!=n;++i){
    scanf("%d", &nums[i]);
  }
  printf("%d\n",solve(0,n-1,nums,memo));
}

牛客题目