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:=