关键词：
Problem:https://www.nowcoder.com/question/next?pid=2811407&qid=46573&tid=6015849
如果一个数字序列逆置之后跟原序列是一样的就称这样的数字序列为回文序列。例如：
{1, 2, 1}, {15, 78, 78, 15} , {112} 是回文序列,
{1, 2, 2}, {15, 78, 87, 51} ,{112, 2, 11} 不是回文序列。
现在给出一个数字序列，允许使用一种转换操作：
选择任意两个相邻的数，然后从序列移除这两个数，并用这两个数字的和插入到这两个数之前的位置(只插入一个和)。
现在对于所给序列要求出最少需要多少次操作可以将其变成回文序列。
输入描述:
输入为两行，第一行为序列长度n ( 1 ≤ n ≤ 50) 第二行为序列中的n个整数item[i] (1 ≤ iteam[i] ≤ 1000)，以空格分隔。
输出描述:
输出一个数，表示最少需要的转换次数
输入例子:
4 1 1 1 3
输出例子:
2
Solution1:
a[i]~a[i+j]变成回文序列，有三种方法：
1.a[i]~a[i+j]合并成一个数
2.a[i]~a[k]，a[k+1]~a[i+j]分别合并成一个数，且两者数值相等
3.a[i]~a[k]合并成一个数，a[l]~a[i+j]合并成一个数,a[k+1]~a[l-1]已构成回文序列，该回文序列长度为f[k+1][l-1]
1 #include <iostream> 2 #define maxn 50 3 #define maxs 1000 4 using namespace std; 5 6 int main() 7 { 8 long n,i,j,k,l,a[maxn+1],f[maxn+1][maxn+1],ans[maxn+1][maxn+1]; 9 cin>>n; 10 for (i=1;i<=n;i++) 11 { 12 cin>>a[i]; 13 ans[i][i]=a[i]; 14 } 15 //the total of a[i]~a[j] 16 for (i=1;i<n;i++) 17 for (j=i+1;j<=n;j++) 18 ans[i][j]=ans[i][j-1]+a[j]; 19 //length:j+1 20 for (j=0;j<=n-1;j++) 21 //begining position:i 22 for (i=1;i<=n-j;i++) 23 { 24 //a[i]~a[i+j]合并成一个数 25 f[i][i+j]=j; 26 //a[i]~a[k]合并成一个数，a[l]~a[i+j]合并成一个数,a[k+1]~a[l-1]已构成回文序列，该回文序列长度为f[k+1][l-1] 27 for (k=i;k<=i+j-2;k++) 28 for (l=k+2;l<=i+j;l++) 29 if (ans[i][k]==ans[l][i+j]) 30 //(k-i)+((i+j)-l)=k+j-l 31 f[i][i+j]=min(f[i][i+j],f[k+1][l-1]+k+j-l); 32 //a[i]~a[k]，a[k+1]~a[i+j]分别合并成一个数，且两者数值相等 33 for (k=i;k<=i+j;k++) 34 if (ans[i][k]==ans[k+1][i+j]) 35 f[i][i+j]=min(f[i][i+j],j-1); 36 } 37 cout<<f[1][n]<<endl; 38 return 0; 39 }
Solution2：
贪心
长度为n的数列(a[1],a[2],……,a[n]) [1 ≤ a[i] ≤ 1000] 经过变换构成回文序列(b[1],b[2],……,b[m])：
设包含a数列元素个数最少的b[1]为：b[1]=a[1]+a[2]+……+a[p],对应的b[m]=a[q]+a[q+1]+……+a[n]
因为a[i]>0，所以q不同，则b[m]不同，所以b[m]具有唯一性。
当存在p‘，使得p‘>p，且b[1]‘=a[1]+a[2]+……+a[p‘],b[m]‘=a[q‘]+a[q‘+1]+……+a[n], b[1]‘=b[m]‘，
有b[m]‘=b[1]‘>b[1]=b[m],即q‘<q，且a[p+1]+……+a[p‘]=a[q‘]+……+a[q-1]。
当某回文序列b[1]‘=a[1]+a[2]+……+a[p‘]，b[m]‘=a[q‘]+a[q‘+1]+……+a[n]，
可以修改b[1]‘为:b[1]=a[1]+a[2]+……+a[p],修改b[m]‘为:b[m]=a[q]+a[q+1]+……+a[n]
修改b[2]‘为:b[2]=b[2]‘+a[p+1]+……+a[p‘],修改b[m-1]为:b[m-1]‘=b[m-1]+a[q‘]+……+a[q-1]。
修改后仍为回文序列，且操作次数与修改前相同。
同理可以把b[2]‘修改为b[2](包含a数列元素个数最少),把b[3]‘修改为b[3](包含a数列元素个数最少),依次类推，直到修改后剩下的数能构成回文序列，且被修改的部分(左/右)构成回文序列的部分(左/右)，所以能构成回文序列，节省的操作次数为原来剩下的数还要继续操作变成回文序列的次数。
采用以下方法构成回文序列：
选取包含a数列元素个数最少的b[1]和对应的b[m]，在此基础上选取包含a数列元素个数最少的b[2]和对应的b[m-1]，依次类推，直到a所有的元素被选取完毕。
上述已证明任意方法能转变成此方法，此方法必不会增加操作次数(操作次数与修改前相同)，且有可能节省操作次数，所以能证明得到用此方法构成回文序列操作次数最小。
#include <iostream> #define maxn 50 using namespace std; int main() { long n,a[maxn+1],i,l,r,ans=0; cin>>n; for (i=1;i<=n;i++) cin>>a[i]; l=1; r=n; while (l<r) { if (a[l]==a[r]) { l++; r--; } else if (a[l]<a[r]) { l++; a[l]+=a[l-1]; ans++; } else { r--; a[r]+=a[r+1]; ans++; } } cout<<ans<<endl; return 0; }
2017网易秋招编程集合
CPPhttp://blog.csdn.net/achiberx/article/details/74058208 [编程题]回文序列如果一个数字序列逆置之后跟原序列是一样的就称这样的数字序列为回文序列。例如：{1,2,1},{15,78,78,15},{112}是回文序列, {1,2,2},{15,78,87,51},{112,2,11}不是... 查看详情
网易2017秋招编程题集合_以下代码全部来自牛客网
如果一个数字序列逆置之后跟原序列是一样的就称这样的数字序列为回文序列。例如：{1,2,1},{15,78,78,15},{112}是回文序列, {1,2,2},{15,78,87,51},{112,2,11}不是回文序列。现在给出一个数字序列，允许使用一种转换操作：选择任意两个... 查看详情
网易2017秋招笔试题3：最长公共子括号序列长度
【问题来源】网传的2017网易秋招笔试题【问题描述】 【算法思路】 下面的解题思路摘自 http://www.cnblogs.com/Atanisi/p/7500186.html刚看到题我就想到暴力解，深搜出所有合法的括号序列，再依次比较公共子序列的长度，返... 查看详情
codeforces607b（dp初步_h题）解题报告
...---------题意：给出一个数字序列，若序列中存在子串存在回文串，可以进行消除，求出最小消除次数。思路：区间dp,对于区间[i,j],如果a[i]==a 查看详情
网易2017秋招---优雅的点
做了这么多的编程题，其实我感觉题目只要找到思路，代码实现是非常容易的，因为程序语言不懂的地方可以百度，而为一个题目找到思路却是没办法搜索的，除非题目是现成可以被搜索的这个题目求解十分容易，用O(n2)的算法... 查看详情
网易秋招校招编程题(代码片段)
网易内推面试凉了，再战正式批笔试，选择和简答略难，编程题很良心，基本就是模拟、找规律，略加思考就能解出来的题目，本弱鸡只有在良心网易笔试才能AK。1、翻转翻转 这题一开始没思路，ac了后两题后再回... 查看详情
网易2017春招笔试真题编程题集合——消除重复元素
时间限制：1秒空间限制：32768K小易有一个长度为n序列，小易想移除掉里面的重复元素，但是小易想是对于每种元素保留最后出现的那个。小易遇到了困难,希望你来帮助他。 输入描述:输入包括两行：第一行为序列长度n(1≤n... 查看详情
美团点评2017秋招笔试编程题
美团点评2017秋招笔试编程题 1， 大富翁游戏，玩家根据骰子的点数决定走的步数，即骰子点数为1时可以走一步，点数为2时可以走两步，点数为n时可以走n步。求玩家走到第n步（n<=骰子最大点数且是方法的唯一入... 查看详情
腾讯2017暑期实习生笔试题解题答案汇总
构造回文题目给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？输出需要删除的字符个数输入描述:输入数据有多组，每组包含一个字符串s，且保证:1... 查看详情
网易2017提前提笔试编程题
1.彩色砖块 小易有一些彩色的砖块。每种颜色由一个大写字母表示。各个颜色砖块看起来都完全一样。现在有一个给定的字符串s,s中每个字符代表小易的某个砖块的颜色。小易想把他所有的砖块排成一行。如果最多存在一对... 查看详情
美团点评2017秋招笔试编程题(代码片段)
C/C++代码1：#include<cstdio>#include<iostream>#include<math.h>intmain()intn;while(scanf("%d",&n)!=EOF)doubleresult=pow(2,n-1);//2的n-1次方printf("%d\n",int(result));return0;C/C++代码 查看详情
2017年腾讯秋招软件开发笔试编程题回忆版
2017年腾讯秋招软件开发笔试编程题回忆版（所有题目大致描述如下，并非完整的题目回忆，但意思大致一样）1、又一个魔法城市，城市里面有n个魔法城堡，序号为0，1，2。。。n-1；魔法城堡之间都有路径相连；魔法城堡两两之... 查看详情
[编程题]操作序列网易2018
小易有一个长度为n的整数序列,a_1,...,a_n。然后考虑在一个空序列b上进行n次以下操作:1、将a_i放入b序列的末尾2、逆置b序列小易需要你计算输出操作n次之后的b序列。 输入描述:输入包括两行,第一行包括一个整数n(2≤n≤2*10^5),... 查看详情
2017网易秋招--8计算糖果
A,B,C三个人是好朋友,每个人手里都有一些糖果,我们不知道他们每个人手上具体有多少个糖果,但是我们知道以下的信息：A-B,B-C,A+B,B+C.这四个数值.每个字母代表每个人所拥有的糖果数.现在需要通过这四个数值计算出每个人手里有... 查看详情
腾讯2017暑期实习生编程题第一题构造回文(代码片段)
给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？输出需要删除的字符个数。输入描述:输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.输出描述:对... 查看详情
滴滴出行秋招编程题
...自己，手贱。 刷头条看到一篇文章写的滴滴出行2017秋招编程题，后来发现原文在这里http://www.cnblogs.com/SHERO-Vae/p/5882357.html。看了下，挺有意思，于是就想了想，又写了写，最终撸出来了。刚开始一看顿时感觉很熟悉，大学数... 查看详情
美团点评2017秋招笔试编程题——大富翁游戏
大富翁游戏，玩家根据骰子的点数决定走的步数，即骰子点数为1时可以走一步，点数为2时可以走两步，点数为n时可以走n步。求玩家走到第n步（n<=骰子最大点数且是方法的唯一入参）时，总共有多少种投骰子的方法。 输... 查看详情
网易2017春招笔试真题编程题集合——分饼干
参考：http://blog.csdn.net/wwe4023/article/details/70171648的内容//importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannerin=newScanner(System.in);Stringline=in.nextLine();intn=Integer. 查看详情