定义dp[t][x1][y1][x2][y2]为在t时刻，人走到x1,y1,影子走到x2,y2所获得最大价值
最终就是所有的dp[max][..][..][..][..]的最大值
然后递推也很自然，枚举人和影子的动向，唯一注意的是当走到一点时，只获得一次价值，要除以2
然后对于每一层时间，其实有效的很少，所以用bfs取有效点更新，这样可以减少一些时间复杂度，最终跑出来1593ms
#include <stdio.h> #include <iostream> #include <vector> #include <math.h> #include <queue> #include <algorithm> #include <string.h> #include <string> using namespace std; typedef long long LL; const int N=1e2+5; const int INF=0x3f3f3f3f; int dx[5]= {0,0,0,-1,1}; int dy[5]= {0,-1,1,0,0}; char s[15][15]; int mp[202][11][11]; int dp[202][11][11][11][11]; bool vis[202][11][11][11][11]; int n,m,p,mx; struct Node { int t,x,y,k1,k2; Node() {} Node(int a,int b,int c,int d,int e) { t=a,x=b,y=c,k1=d,k2=e; } }; queue<Node>q; void bfs() { memset(dp,-1,sizeof(dp)); memset(vis,0,sizeof(vis)); while(!q.empty())q.pop(); dp[0][1][1][1][1]=0; vis[0][1][1][1][1]=1; Node a,tmp; q.push(Node(0,1,1,1,1)); while(!q.empty()) { a=q.front(); q.pop(); if(a.t==mx)continue; tmp.t=a.t+1; int o=dp[a.t][a.x][a.y][a.k1][a.k2]; for(int i=0; i<5; ++i) for(int j=0; j<5; ++j) { tmp.x=a.x+dx[i],tmp.y=a.y+dy[i]; tmp.k1=a.k1+dx[j],tmp.k2=a.k2+dy[j]; if(tmp.x<1||tmp.x>n||tmp.y<1||tmp.y>m)continue; if(tmp.k1<1||tmp.k1>n||tmp.k2<1||tmp.k2>m)continue; if(s[tmp.x][tmp.y]=='#'||s[tmp.k1][tmp.k2]=='#')continue; int c=mp[tmp.t][tmp.x][tmp.y]+mp[tmp.t][tmp.k1][tmp.k2]; if(tmp.x==tmp.k1&&tmp.y==tmp.k2)c/=2; c+=o; if(c>dp[tmp.t][tmp.x][tmp.y][tmp.k1][tmp.k2]) { dp[tmp.t][tmp.x][tmp.y][tmp.k1][tmp.k2]=c; if(!vis[tmp.t][tmp.x][tmp.y][tmp.k1][tmp.k2]) { q.push(tmp); vis[tmp.t][tmp.x][tmp.y][tmp.k1][tmp.k2]=1; } } } } } int main() { int T; scanf("%d",&T); while(T--) { mx=0; scanf("%d%d",&n,&m); for(int i=1; i<=n; ++i) scanf("%s",s[i]+1); memset(mp,0,sizeof(mp)); scanf("%d",&p); for(int i=0; i<p; ++i) { int t,x,y,v; scanf("%d%d%d%d",&t,&x,&y,&v); mx=max(mx,t); mp[t][x][y]+=v; } bfs(); int ans=0; for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) for(int k1=1; k1<=n; ++k1) for(int k2=1; k2<=m; ++k2) ans=max(ans,dp[mx][i][j][k1][k2]); printf("%d ",ans); } return 0; }