題意

在一個n*n的網(wǎng)格中，在某些時刻鼴鼠會在某一個網(wǎng)格探出頭來透透氣。你可以控制一個機器人來打鼴鼠，如果i時刻鼴鼠在某個網(wǎng)格中出現(xiàn)，而機器人也處于同一網(wǎng)格的話，那么這個鼴鼠就會被機器人打死。而機器人每一時刻只能夠移動一格或停留在原地不動。機器人的移動是指從當(dāng)前所處的網(wǎng)格移向相鄰的網(wǎng)格，即從坐標為（i,j）的網(wǎng)格移向(i-1, j),(i+1, j),(i,j-1),(i,j+1)四個網(wǎng)格，機器人不能走出整個n*n的網(wǎng)格。現(xiàn)在你知道在一段時間內(nèi)，鼴鼠出現(xiàn)的時間和地點，希望你編寫一個程序使機器人在這一段時間內(nèi)打死盡可能多的鼴鼠。?

分析

f[i]:=f[j]+1;(abs(x[i]-x[j])+abs(y[i]-y[j])<=time[i]-time[j])；

var
i,j,n,m,tj:longint;
time,x,y,f:array[0..10000]of longint;


function max(a,b:longint):longint;
begin
? ? if a>b then exit(a) else exit(b);
end;
begin
? ? readln(n,m);
? ? for i:=1 to m do
? ? readln(time[i],x[i],y[i]);
? ? for i:=1 to m do
? ? f[i]:=1;


? ? for i:=1 to m do
? ? for j:=1 to i-1 do
? ? if (abs(x[i]-x[j])+abs(y[i]-y[j])<=time[i]-time[j]) then f[i]:=max(f[i],f[j]+1);


? ? tj:=0;
? ? for i:=1 to m do
? ? tj:=max(tj,f[i]);
? ? write(tj);
end.

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9500165.html

總結(jié)

以上是生活随笔為你收集整理的打鼹鼠的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。