axj)设为下一个采集目标(max1i←maxi;max1j←maxj)。?重复上述计算过程,直至花生田里无花生(max=0)或者采集(max1i,max1j)位置的花生后无法返回路边(t+max1i-1>k)为止。由此得出算法:Рreadln(m,n,k);{读花生田的规模和多多采花生的限定时间}?k←k-2; {计算多多在数组内采集花生的最多时间}?max←0;{读花生田的信息。计算花生数最多的位置(max1i,max1j)和该位置的花生数max}?for i←1 to m do? for j←1 to n do? begin? read(p[i,j]);? if p[i,j]>max then begin max←p[i,j];max1i←i;max1j←j;end;{then}? end;{for}?t←max1i;total←0;{ 多多的行程和采集的花生数初始化}?while (t+max1i-1<=k)and(max>0) do{若在限定时间内回到路边且找到花生最多的植株,则采摘它的花生,并累计采摘的花生总数}? begin? p[max1i,max1j]←0;total←total+max;? max←0;{计算当前花生数最多的位置(maxi,maxj)和该位置的花生数max}? for i←1 to m do? for j←1 to n do if p[i,j]>max then begin max←p[i,j];maxi←i;maxj←j;end;{then}? t←t+1+abs(max1i-maxi)+abs(max1j-maxj);{累计行程}? max1i←maxi;max1j←maxj;{从该位置出发,继续采摘花生}?end;{while}? writeln(total);{输出限定时间内多多采到花生数的最大值} ?时间复杂度为O (k*n2)
全文预览
