GDSOI2014曹刿论战

1、GDSOI 2014 曹刿论战小明很喜欢读历史故事。有一天，他在读左传的时候，读到那么一则故事：曹刿（guì）论战。这则故事讲的时在春秋时期的长勺之战。当时，强大的齐国要来攻打弱小的鲁国。曹刿作主动请求一旁分析战况，结果一举帮助鲁庄公，歼灭来敌。可以说是一场经典的以弱胜强的战役。曹刿有多厉害呢？他通过观察敌人的凌乱的足迹准确地判断出了敌人的形势，做出了正确的决策。这则故事告诉我们，细致选择进攻时机，知己知彼的重要性。小明很喜欢这则故事，现在他想，是否能从一段路上敌人的脚印推算出最少有多少人在逃亡呢？这真是一个十分有趣的问题。不过考虑到实际的问题复杂性，我们稍微简化了一下背景：1.这段

2、路落在一个坐标轴上，每个点可以用一个数值表示2.假设每个士兵都是向坐标轴正方向逃亡，不会往回走3. 对于任意一个士兵，他相邻的两步之间距离为L（1<=L<=50），但不同的士兵可能有不同的步幅。4.显然的，每个士兵的脚印是左右脚交替的5.因为，在每个士兵逃亡的过程中，留下的脚印都是很多的，为了很好地分析问题，我们决定，只选择0-199这部分的脚印，进行分析6.保证每个士兵都不会从0-199的范围内开始逃亡，也不会停在0-199的范围内。举例来说，对于一个士兵，他的步长为50，假设他的脚印有（50，0），（100，1），那么肯定有脚印（0，1）（因为他不可能从坐标为50的地方出发），

3、也肯定有（150，0）（因为他不可能停留在坐标为100的地方）。现在我们记录了N个脚印的坐标x，还有它是左脚还是右脚（y=0代表左脚，y=1代表右脚）。现在请问最少有多少个人经过这段路呢？Input本题有多组数据，但数据组数不超过10，对于每一组数据。第一行输入一个整数N,表示脚印的数量，之后的第二行到第N+1行，每一行有2个整数x和y，x为这个脚印的x坐标，y为0表示是左脚，而1表示是右脚。Output对于每组数据输出一行，一个整数M，表示最少的可能经过这段路的人数Sample Input100 120 040 160 080 1100 0120 1140 0160 1180 0110 13

4、0 030 060 180 190 0120 1130 0150 0180 1180 1Sample Output1240%的数据：N<=250，0<=x<200，0<=y<=1，答案M<=10100%的数据：N<=800，0<=x<200，0<=y<=1，答案M<=25CODE:Uses Math;Const Maxn=3000;Var way: array0.maxn,0.200,0.1of Longint; tot: array0.200,0.1of Longint; t: array0.maxnof Longint

5、; n,m,rem,xx,yy,ans,sav: Longint; ok: Boolean;procedure fw(k: Longint);Var i,j,x,y,z,tmp: Longint;Begin Inc(m); waym00:=0; x:=xx; z:=k; While (x<=199) Do Begin if totxz=0 Then Begin Dec(m); Break; End; Inc(waym00); waymwaym000:=x; waymwaym001:=z; Inc(x,yy); if z=0 Then z:=1 Else z:=0; End;End;Pro

6、cedure Init();Var i,j,x,y: Longint;Begin Fillchar(tot,sizeof(tot),0); Readln(n); m:=0; For i:=1 To n Do Begin Readln(x,y); totxy:=totxy+1; End; For i:=1 To 50 Do For j:=0 To i-1 Do Begin xx:=j; yy:=i; fw(0); fw(1); End;End;Procedure dfs(x,y: Longint);Var i,j: Longint;Begin if rem=0 Then Begin ans:=M

7、in(ans,y); Exit; End; if x=m Then Exit; Inc(x); if (y+(rem-1) Div tx+1>=ans)or(rem<waym00) Then Exit; ok:=True; For i:=1 To wayx00 Do Begin if totwayxi0wayxi1=0 Then Begin ok:=False; Break; End; End; if ok Then Begin For i:=1 To wayx00 Do Dec(totwayxi0wayxi1); Dec(rem,wayx00); Dfs(x-1,y+1); Inc(rem,wayx00); For i:=1 To wayx00 Do Inc(totwayxi0wayxi1); End; Dfs(x,y);End;Procedure Main();Var i,j: Longint;begin rem:=n; Fillchar(t,sizeof(t),0); For i:=m Downto 1 Do ti:=Max(wayi00,ti+1); ans:=