如果一个数字序列逆置之后跟原序列是一样的就称这样的数字序列为回文序列。例如:
{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 ≤ item[i] ≤ 1000),以空格分隔。
输出一个数,表示最少需要的转换次数
4 1 1 1 3
2
经过第一次操作后,变为2 1 3,{2, 1, 3} 不是回文序列; 再经过一次操作后,变为3 3,{3, 3} 是回文序列; 所以共需要进行两次转换。
#首尾指针跟踪 #两个数不相等就进行加法:小的数加上相邻的值 import sys n=int(input()) item=list(map(int,sys.stdin.readline().strip().split())) ans=0 head=0 tail=n-1#首尾指针 left = item[head] right = item[tail]#首尾指针指向的数 while (head<tail): if left<right:#左小于右,左边的数加上他旁边的数 head+=1 left+=item[head] ans+=1 continue elif left>right:#左大于右,右边的数加上它旁边的树 tail-=1 right+=item[tail] ans+=1 continue else: #左等于右时,首尾指针各往中间移一位 head+=1 tail-=1 left = item[head] right = item[tail] print(ans)
#不用递归!--人生苦短我用python #首尾指针跟踪 #两个数不相等就进行加法:小的数加上相邻的值 n = int(raw_input().strip()) item = [int(x) for x in raw_input().strip().split()] def huiwen(item, head, tail): times=0 left = item[head] right = item[tail] while (head<tail): if left<right: head+=1 left+=item[head] times+=1 continue elif left>right: tail-=1 right+=item[tail] times+=1 continue elif left==right: head+=1 tail-=1 left = item[head] right = item[tail] return times print huiwen(item,0,n-1)
def comb(num,head,tail): times=0 left=num[head] right=num[tail] while(head<tail and left!=right): if(left<right): head+=1 left+=num[head] times+=1 else: tail-=1 right+=num[tail] if(head>=tail): return times else: while(head<tail): head+=1 tail-=1 times+=comb(num,head,tail) return times N=input('') line=raw_input('') num=line.split(' ') print comb(num,head=0,tail=N)