【ZOJ2278】Fight for Food（dp）

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;

}