第25届宁波市中小学生程序设计竞赛（初中组）复赛第三题——插入排序

const maxn=100000maxm=20000

var a:array[1..maxn]of longint

c,lowbit:array[1..maxm]of longint

n,i,j,sum,max,tmp:longint

function findmax(i:longint):longint

var max:longint

begin

max:=0

while i>0 do begin

if max<c[i] then max:=c[i]

i:=i-lowbit[i]

end

findmax:=max

end

procedure fill(i,x:longint)

begin

while i<=maxm do begin

if c[i]<x then c[i]:=x

i:=i+lowbit[i]

end

end

begin

assign(input,'insert.in')reset(input)

assign(output,'insert.out')rewrite(output)

for i:=1 to maxm do lowbit[i]:=i and (i xor (i-1))

read(n)

for i:=1 to n do read(a[i])

sum:=0

for i:=1 to n do sum:=sum+a[i]

fillchar(c,sizeof(c),0)

max:=0

for i:=1 to n do begin

tmp:=findmax(a[i])

tmp:=tmp+a[i]

if max<tmp then max:=tmp

fill(a[i],tmp)

end

writeln(sum-max)

close(output)close(input)

end.

ACM国家大学生竞赛自1996年起设立中国大陆地区预选赛赛区，并由上海大学承办，至2001年总决赛止，连续举办五届。之后在境内设置多个赛点，由各大学轮流主办地区性竞赛至今。

历年中国大陆举办区域赛地点： 年份 1996年 上海大学 　1997年 上海大学 　1998年 上海大学 　1999年 上海大学 　2000年 上海大学 　2001年 上海大学 　2002年 清华大学 西安交通大学 2003年 清华大学 中山大学 2004年 上海交通大学 北京大学 2005年 四川大学 北京大学 浙江大学 　2006年 上海大学 清华大学 西安电子科技大学 　2007年 西华大学 南京航空航天大学 北京航空航天大学 吉林大学 2008年 中国科学技术大学(特别赛区) 北京交通大学 哈尔滨工程大学 杭州电子科技大学 西南民族大学 　2009年 浙江大学宁波理工学院 中国科学技术大学 东华大学 哈尔滨工业大学 武汉大学 　2010年 哈尔滨工程大学 天津大学 四川大学 浙江理工大学 福州大学 　2011年 大连理工大学 复旦大学 北京邮电大学 成都东软学院 福建师范大学 　2012年 东北师范大学天津理工大学 浙江师范大学 浙江理工大学 成都东软学院 　2013年吉林大学南京理工大学浙江工业大学电子科技大学湖南大学 　2014年牡丹江师范学院辽宁科技大学西北工业大学华南理工大学北京师范大学上海大学2015年东北师范大学东北大学中国科学技术大学北京大学华东理工大学上海大学（特别赛区） 由上海交通大学承办的第29届ACM国际大学生程序设计竞赛全球总决赛于2005年4月3-7日期间在上海浦东的香格里拉酒店举行。总共有78支队伍参加总决赛的角逐，它们是从来自6大洲71个国家1582所大学的4109支队伍中通过之前的各级区域预赛中脱颖而出的。在当地时间4月6日上午举行的全球总决赛上，东道主上海交通大学代表队是所有参赛队伍中唯一一支解出8道题目的队伍，从而在时隔3年之后第二次夺得全球总冠军。

由哈尔滨工程大学承办的第34届ACM国际大学生程序设计竞赛全球总决赛于2010年2月在哈尔滨举行，上海交通大学再次夺冠。