题目描述:
如果一个数字序列逆置之后跟原序列是一样的就称这样的数字序列为回文序列。例如：
{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
示例代码如下：
#include<iostream>
#include<deque>
using namespace std;
//根据题目所述：利用双端队列来解决该问题较好--直观清晰。
//当然，使用vector,list也可以。
//如果一个序列是非回文序列，
//那么首先肯定要找到数列的不对称端的较小的元素，
//接着将该元素以及与其相邻的元素取出，并相加。
//同时，让操作次数加1。
//将相加结果再次放入取出端（队列的最长度减少1），并与另一端对应元素相比较。
//如果相等，则将两个端元素弹出（队列的总长度减少2）。如果不相等，则继续上述过程。
//直到队列为空。
int main()
{
int N;//序列的长度
while(cin >> N)
{
//完成序列输入
deque<int> deq;
deq.clear();
int temp;
for(int i=0; i < N; ++i)
{
cin >> temp;
deq.push_back(temp);
}
int nCount=0;//统计操作次数
int n1,n2;
while(deq.size() > 1)
{//要特别注意：队列中剩余1个或者0个元素均表示：统计结束
if(deq.front() == deq.back())
{//两端的元素对称，满足回文序列的特点
//直接弹出两端的元素即可
deq.pop_back();
deq.pop_front();
}
else
{//两端元素不对称
if(deq.front() < deq.back())
{//前端的元素较小
//同时取出前端的两个元素
n1 = deq.front();
deq.pop_front();
n2 = deq.front();
deq.pop_front();
//相加
temp =n1 + n2;
//放入队列前端
deq.push_front(temp);
nCount++;
}
else
{//后端元素较小
//同时取出后端的两个元素
n1 = deq.back();
deq.pop_back();
n2 = deq.back();
deq.pop_back();
//相加
temp = n1 + n2;
//放入队列后端
deq.push_back(temp);
nCount++;
}
}
}
cout << nCount << endl;
}
return 0;
}
