P2285 [HNOI2004]打鼴鼠

題目描述

鼴鼠是一種很喜歡挖洞的動(dòng)物，但每過一定的時(shí)間，它還是喜歡把頭探出到地面上來透透氣的。根據(jù)這個(gè)特點(diǎn)阿牛編寫了一個(gè)打鼴鼠的游戲：在一個(gè)n*n的網(wǎng)格中，在某些時(shí)刻鼴鼠會(huì)在某一個(gè)網(wǎng)格探出頭來透透氣。你可以控制一個(gè)機(jī)器人來打鼴鼠，如果i時(shí)刻鼴鼠在某個(gè)網(wǎng)格中出現(xiàn)，而機(jī)器人也處于同一網(wǎng)格的話，那么這個(gè)鼴鼠就會(huì)被機(jī)器人打死。而機(jī)器人每一時(shí)刻只能夠移動(dòng)一格或停留在原地不動(dòng)。機(jī)器人的移動(dòng)是指從當(dāng)前所處的網(wǎng)格移向相鄰的網(wǎng)格，即從坐標(biāo)為（i,j）的網(wǎng)格移向(i-1, j),(i+1, j),(i,j-1),(i,j+1)四個(gè)網(wǎng)格，機(jī)器人不能走出整個(gè)n*n的網(wǎng)格。游戲開始時(shí)，你可以自由選定機(jī)器人的初始位置。

現(xiàn)在知道在一段時(shí)間內(nèi)，鼴鼠出現(xiàn)的時(shí)間和地點(diǎn)，請(qǐng)編寫一個(gè)程序使機(jī)器人在這一段時(shí)間內(nèi)打死盡可能多的鼴鼠。

輸入輸出格式

輸入格式：

?

從文件input.txt中讀入數(shù)據(jù)，文件第一行為n（n<=1000）, m（m<=10000），其中m表示在這一段時(shí)間內(nèi)出現(xiàn)的鼴鼠的個(gè)數(shù)，接下來的m行中每行有三個(gè)數(shù)據(jù)time,x,y表示有一只鼴鼠在游戲開始后time個(gè)時(shí)刻，在第x行第y個(gè)網(wǎng)格里出現(xiàn)了一只鼴鼠。Time按遞增的順序給出。注意同一時(shí)刻可能出現(xiàn)多只鼴鼠，但同一時(shí)刻同一地點(diǎn)只可能出現(xiàn)一只鼴鼠。

?

輸出格式：

?

輸出文件output.txt中僅包含一個(gè)正整數(shù)，表示被打死鼴鼠的最大數(shù)目。

?

輸入輸出樣例

輸入樣例#1： 2 2 1 1 1 2 2 2 輸出樣例#1： 1

分析

dp，f[i]表示到第i個(gè)鼴鼠時(shí)能打多少個(gè)狀態(tài)轉(zhuǎn)移方程：f[i] = max(f[i],f[j]+1)， 條件:abs(x[i]-x[j])+abs(y[i]-y[j])<=abs(t[i]-t[j]) 轉(zhuǎn)為序列dp，比較好處理。

代碼

1 #include<cstdio> 2 #include<algorithm> 3 #include<cstdlib> 4 #include<cmath> 5 using namespace std; 6 int x[10010],y[10010],t[10010],f[10010]; 7 int n,m,ans = 0; 8 int read() 9 { 10 int x=0,f=1;char ch=getchar(); 11 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0'&& ch<='9'){x=x*10+ch-'0';ch=getchar();} 13 return x*f; 14 } 15 int main() 16 { 17 18 n = read(); m = read(); 19 for (int i=1; i<=m; ++i) 20 { 21 t[i] = read();x[i] = read();y[i] = read(); 22 } 23 for (int i=1; i<=m; ++i) 24 { 25 f[i] = 1; 26 for (int j=1; j<i; ++j) 27 if (abs(x[i]-x[j])+abs(y[i]-y[j])<=abs(t[i]-t[j])) f[i] = max(f[i],f[j]+1); 28 ans = max(ans,f[i]); 29 } 30 printf("%d",ans); 31 return 0; 32 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/mjtcn/p/7107279.html

總結(jié)

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

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