【ZOJ2278】Fight for Food（dp）---饶文津

题意

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

题解

代码#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("%dn",ans); } return 0; } ---来自腾讯云社区的---饶文津