【正文】 assign(f2,39。)。 {初始化} init。 ans:=[]。 fillchar(min,sizeof(min),0)。 min[j,0]:=data[j]。 {初值是不經(jīng)過(guò)運(yùn)算(l=0)的值} for l:=1 to n1 do {考慮長(zhǎng)度由1到n1} for k:=1 to n do {考慮起始點(diǎn)從1到n} begin max[k,l]:=maxint1。 for t:=0 to l1 do {考慮分開(kāi)前半部分經(jīng)過(guò)的運(yùn)算數(shù)} begin case sign[(k+t+11) mod n+1] of {考慮分開(kāi)處的符號(hào)} 39。: {為加法} begin if max[k,t]+max[(k+t+11) mod n+1,lt1]max[k,l] then max[k,l]:=max[k,t]+max[(k+t+11) mod n+1,lt1]。 {最小值更新} end。x39。 2: s:=max[k,t]*min[(k+t+11) mod n+1,lt1]。 4: s:=min[k,t]*min[(k+t+11) mod n+1,lt1]。 if smax[k,l] then max[k,l]:=s。 {更新最大最小值} end。 end。 end。 ans:=[i] end else if max[i,n1]=best then include(ans,i)。 {輸出最大值} first:=true。 39。 write(f2,i)。 writeln(f2)。 close(f2) {關(guān)閉文件}end. {結(jié)束}程序4 ACM’97亞洲區(qū)/上海賽題 正則表達(dá)式匹配program Expression_Match。 {起始、結(jié)束字符} md:0..1。 {匹配方式 0：不包含為匹配；1：包含為匹配} end。 {文件變量} s1,s2:string。 len:integer。 {預(yù)處理結(jié)果} pro:array [0..80,0..80] of boolean。 {FR[i,j]表示以第j個(gè)字符為尾的與前i項(xiàng)正則表達(dá)式匹配的最前端的字符位置} i,j,k,l:integer。 {找到標(biāo)記} ha:boolean。 bt,bj:integer。 {預(yù)處理，生成規(guī)劃的“正則表達(dá)式”表示}var i,j,k:integer。begin i:=0。 while ilength(s1) do begin inc(i)。.39。 dd[j].md:=0。 dd[j].st:=0。 end。*39。 {處理“*”} 39。: {處理“+”} begin inc(j)。 dd[j].md:=1。 39。: {處理“\”} begin inc(i)。 dd[j].md:=0。 dd[j].st:=s1[i]。 end。[39。 inc(j)。 dd[j].mt:=1。^39。 dd[j].mt:=0 end。\39。 dd[j].st:=s1[i]。 if s1[i]=39。 then inc(i)。 inc(i)。 dd[j].st:=s1[i]。 dd[j].mt:=1。 end。 end。begin assign(f1,39。)。 assign(f2,39。)。 {文件關(guān)聯(lián)、打開(kāi)} while true do begin readln(f1,s1)。end39。 {如果為end串，跳出} readln(f1,s2)。 {預(yù)處理} ok:=false。 fillchar(pro[0],sizeof(pro[0]),true)。 bt:=maxint。 for i:=0 to length(s2) do {賦初值} fr[0,i]:=i+1。 {與去掉這個(gè)字母后的結(jié)果一致} if pro[i,j] then fr[i,j]:=fr[i1,j1]。 for k:=j downto 0 do {考慮前i1項(xiàng)正則表達(dá)式與前若干項(xiàng)字符串匹配情況} begin if pro[i1,k] then {如果某個(gè)為真} begin pro[i,j]:=true。 {如果起點(diǎn)較早，更新之} end。 break end。 end。 bt:=fr[i,j]。 end。if ok then if bj0 then writeln(f2,copy(s2,1,bt1), 39。, copy(s2,bt,bj), 39。, copy(s2,bt+bj,length(s2)btbj+1)) {如果找到，輸出} else writeln(f2,’()’,s2) {對(duì)于某些理論上講可以與空串匹配的正則表達(dá)式，應(yīng)看作與第一個(gè)字符前的空串匹配，這里作了專門處理} else writeln(f2,s2)。 close(f1)。{免費(fèi)餡餅 將允許時(shí)間擴(kuò)大到3000秒，分值限制在longint范圍內(nèi)}type link=^linetype。 {記錄一個(gè)時(shí)間單位決策的數(shù)組}var f1,f2:text。 {寬度、高度} dd:array [0..100] of array [1..99] of longint。 {記錄決策信息的動(dòng)態(tài)數(shù)組} dt:array [0..1,1..99] of longint。 {輔助變量} bt,bj:integer。 {最大值記錄} maxt:integer。 {倒推答案時(shí)用的暫存區(qū)} num:integer。 _t,_j,_v:integer。 {暫存分值} _saved:boolean。 {讀入原始數(shù)據(jù)的過(guò)程，其中使用了分段讀取的方法。 {初始下落時(shí)間} fz:longint。 {t及以后時(shí)間讀入的塊，至遲在t+99時(shí)間即進(jìn)入可接收狀態(tài)，可對(duì)t+100(循環(huán)觀點(diǎn)下)單元清0，以便下次使用} if _saved then {如果上次有預(yù)存} begin if _tt then exit。 if (h1) mod _v=0 then begin inc(dd[(_t+(h1) div _v) mod 101,_j],_fz)。 end。 if eof(f1) then exit。 readln(f1,t0,j,v,fz)。 _t:=t0。 _fz:=fz。 exit {暫存返回} end。 {標(biāo)記時(shí)間位置與得到的分值} inc(dd[(t0+(h1) div v) mod 101,j],fz)。 end。begin {主程序} assign(f1,39。)。 assign(f2,39。)。 {文件關(guān)聯(lián)、打開(kāi)} readln(f1,w,h)。 fillchar(pro[i]^,sizeof(pro[i]^),0)。 for i:=0 to 1 dofor j:=1 to 99 do dt[i,j]:=maxlongint1。 {maxlongint1表示該點(diǎn)不可達(dá)} fillchar(dd,sizeof(dd),0)。 maxt:=0。 try_reading。 bt:=0。 best:=dd[0,(w+1) div 2]。 {考慮下一個(gè)時(shí)間} try_reading。 {如果沒(méi)有新的數(shù)據(jù)，跳出} for j:=1 to w do {考慮各個(gè)位置} begin dt[t mod 2,j]:=maxlongint1。 {更新當(dāng)前最優(yōu)值} pro[t]^[j]:=k。 if dt[t mod 2,j]best then {如果到目前最優(yōu)，更新之} begin best:=dt[t mod 2,j]。 bj:=j。 end。 writeln(f2,best)。 j:=bj。 inc(j,pro[t]^[j])。 for t:=1 to bt do writeln(f2,ans[t])。 close(f2)end.論文附錄： 本文所引題目詳細(xì)內(nèi)容字符識(shí)別 (IOI’97)Character RecognitionThis problem requires you to write a program that performs character recognition.Details:Each ideal character image has 20 lines of 20 digits. Each digit is a ‘0’ or a ‘1’. See Figure 1a for the layout of character images in the file.The file contains representations of 27 ideal character images in this order: oabcdefghijklmnopqrstuvwxyzwhere o represents the space character.The file contains one or more potentially corrupted character images. A character image might be corrupted in these ways:* at most one line might be duplicated (and the duplicate immediately follows)* at most one line might be missing* some ‘0’ might be changed to ‘1’* some ‘1’ might be changed to ‘0’.No character image will have both a duplicated line and a missing line. No more than 30% of the ‘0’ and ‘1’ will be changed in any character image in the evaluation datasets.In the case of a duplicated line, one or both of the resulting lines may have corruptions, and the corruptions may be different.Task:Write a program to recognise the sequence of one or more characters in the image provided in file using the font provided in file .Recognise a character image by choosing the font character images that require the smallest number of overall changed ‘1’ and ‘0’ to be corrupted to the given font image, given the most favourable assumptions about duplicated or omitted lines. Count corruptions in only the least corrupted line in the case of a duplicated line. All characters in the sample and evaluation images used are recognisable onebyone by a wellwritten program. There is a unique best solution for each evaluation dataset.A correct solution will use precisely all of the data supplied in the input file.Input:Both input files begin with an integer N (19N160