BUPT2017 wintertraining(16) #4 F

ZOJ - 2278

题意

给定一个10*10以内的地图,和p(P<=30000)只老鼠,给定其出现位置和时间T(T<=1,000,000,000),求最多抓到几只老鼠。

题解

DP,f[i]表示按时间排序后抓第i个老鼠,最多能抓多少只。

bfs计算每对位置之间的距离\(dis[x1][y1][x2][y2]\)。

\(f[i]=max(f[i],f[j]+1)\)当i,j两只老鼠的距离小于他们的时间差。

j只用往前枚举50就够了,因为总共就10*10的地图。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define N 30005
#define inf 0x3f3f3f3f
using namespace std;
struct node{int x,y,t;}a[N];
int n,m,p;
int f[N],ans;//经过第i个最多经过几个
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int mm[20][20];
int dis[20][20][20][20];
bool cmp(const node& a,const node& b){
return a.t<b.t;
}
void bfs(int x,int y){
dis[x][y][x][y]=0;
queue<node>q;
q.push((node){x,y});
while(!q.empty()){
node k=q.front();
q.pop();
for(int i=0;i<4;i++){
int nx=k.x+dx[i],ny=k.y+dy[i];
if(nx>=0&&ny>=0&&nx<n&&ny<m&&mm[nx][ny]
&&dis[x][y][nx][ny]==inf){
dis[x][y][nx][ny]=dis[x][y][k.x][k.y]+1;
q.push((node){nx,ny});
}
}
}
}
int main() {
while(~scanf("%d%d",&n,&m)){
memset(f,-inf,sizeof f);
memset(dis,inf,sizeof dis);
f[0]=ans=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
char c;
scanf(" %c",&c);mm[i][j]=(c!='#');
if(c=='L')a[0]=(node){i,j,0};
}
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)if(mm[i][j])bfs(i,j);
scanf("%d",&p);
for(int i=1;i<=p;i++){
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].t);
a[i].x--;a[i].y--;
}
sort(a+1,a+1+p,cmp);
for(int i=1;i<=p;i++){
for(int j=max(i-50,0);j<i;j++){
if(f[j]!=-inf&&dis[a[j].x][a[j].y][a[i].x][a[i].y]<=a[i].t-a[j].t)
f[i]=max(f[i],f[j]+1);
}
ans=max(f[i],ans);
}
printf("%d\n",ans);
}
return 0;
}
05-11 08:33