题目描述

czm 非常喜欢回文数列。回文数列是指一个包含 N 个整数的数列 A ，分别为 A[1],A[2],……,A[n]，对于第 i (1<=i<=N) 个数 A[i] ，都有 A[i] = A[N-i+1] 。但是回文数字非常难得到。

现在 czm 想到了一个办法，他可以将数列中，任意两个相邻的数字合并，用它们的和来代替，合并完成的值还可以和其他值不断合并，直到只剩下一个数。要知道一个数肯定是回文数列。

当然， czm 希望他的回文数列尽可能长，因此，请你帮助 czm 计算一下，对于一个长度为 N 的数列，经过最少多少次合并，可以构成一个回文数列。

输入格式

第 1 行一个整数 N ( 1 <= N <= 500000 )，表示数列中整数的个数。

第 2 行包含 N 个正整数，中间用空格分开，表示数列中的数字。

输出格式

输出一个最小合并次数，使得数列变成回文数列。

样例

3
1 2 3

1

5
1 2 4 6 1

1

4
1 4 3 2

2

样例解释

样例1: 将1,2合并得到回文数列 3 3

样例2: 将2,4合并，得到回文数列 1 6 6 1

样例3: 先将1和4合并，得到 5 3 2 ，再将 3 2 合并得到 5 5 是回文数列

程序填空

#include<bits/stdc++.h>
using namespace std;
int n,a[500001],cnt;
int main()
{
	cin>>n;
	int i,r,l;
	
	for(i=1;i<=n;i++)
		cin>>a[i];
	
	//l 代表左指针， r代表右指针
	for(l=1,r=n; l<r ; )
	{
		if(a[l]!=a[r])  //左右两端不相等
		{
			if(a[l]>a[r])  //左大右小
			{
				a[r-1] += 填空(1);
				r--; 
			}
			else if(a[l]<a[r])  //左小右大
			{
				a[l+1] += a[l];
				l++;
			}
			填空(2) ;
		}
		else //左右两端相等
		{
			填空(3) ;
			r--; 
		}
	}
	cout<<cnt;
	return 0;

}

填空1：{{ input(1) }}

填空2：{{ input(2) }}

填空3：{{ input(3) }}

张老师提示

题目的意思是不能调换数字在数列中的位置，唯一的操作就是合并 相邻 的两个数字，操作的最终目标是让数列称为回文数列。

回文数列的定义就是前后对应位置的数字相等， 如果有 n 项，则第 1 项和第 n 项比，第 2 项和第 n - 1 项比。但是，数项合并之后，这个 n 就会变化，合并一次就减少 1

最后一定是能改成一个回文数列的，极端情况下，就是合并成 1 个数字，1 个数字自己和自己比是相等，所以也算是回文数列。只不过，这条题目的意思是希望尽可能的合并次数。

按照回文数列的定义，第 1 项 必须和 最后一项 相等，这是绕不过去的坎，既然绕不过去，我们就先解决第一项和最后一项，然后再循环做下去（第二项和倒数第二项....）。 这是整个程序的关键点，想好了这个问题才能填这几个空

为了让第一项和最后一项相等，而且又希望少一点的合并次数，无非就是让小的数字变大一点（合并），大和小的关系在合并之后可能发生变化的。另外，第一个和最后一个对应的是哪一个，这个关系也是动态变化的。本题用到的是两指针移动法。按照大纲，这个知识点是 4 级的内容，没想到 3 级课程的第 1 题就来这个，不讲武德。