问题描述：

如果一个数字序列逆置后跟原序列是一样的，则称这样的数字序列为回文序列例如：$\left\{1,2,1\right\}、\left\{15,78,78,15\right\}、\left\{11,2,11\right\}$是回文序列，而$\left\{1,2,2\right\}、\left\{15,78,87,51\right\}、\left\{112,2,11\right\}$不是回文序列。现在给出一个数字序列，允许使用一种转换操作：选择任意两个相邻的数，然后从序列中移除这两个数，并将这两个数的和插入到这两个数之前的位置(只插入一个和)

对于所给序列求出最少需要多少次操作可以将其变成回文序列。

输入描述：输入为两行

4 1 1 1 3

样例输出：

2

问题求解：

用 item[low. .high] 表示判断的区间，ie表示前端的数(初始时 ie=item[low])，je表示后端的数(初始时 je=item[high])，ans记录转换操作次数(初始为0)。设 f(low,high) 返回 item[low. .high] 变为回文的操作次数，对应递归模型如下：

f(low,high)=ans 当item[low..high]区间只有一个数或者为空 f(low,high)=ans+f(++low,--high) 当ie=je时 f(low,high)=(ans++)+f(++low,high) 当ie<je,ie=item[low]+item[low+1]时 f(low,high)=(ans++)+f(low,--high) 当ie>=je,je=item[high]+item[high-1]

需要注意的是，后面两种情况可能会重复出现，采用while循环判断，但每次循环是ie总是为item[low. .high]区间首元素，je总是位item[low. .high]区间尾元素

代码：

#include <iostream> using namespace std; int huiwen(int arry[], int low, int high) { int count = 0; int qian = arry[low]; int hou = arry[high]; while (low < high && qian!=hou) { if (qian < hou) { low++; qian += arry[low]; ++count; } else { high--; hou += arry[high]; ++count; } } if (low >= high) { return count; } else { low++; high--; return count + huiwen(arry, low, high); } } int main() { int *arry,n,t; cin >> n; arry = new int[n]; for (int i = 0; i < n; i++) { cin >> arry[i]; } cout << huiwen(arry, 0, n - 1) << endl; }