定义dp[t][x1][y1][x2][y2]为在t时刻，人走到x1,y1,影子走到x2,y2所获得最大价值
最终就是所有的dp[max][..][..][..][..]的最大值
然后递推也很自然，枚举人和影子的动向，唯一注意的是当走到一点时，只获得一次价值，要除以2
然后对于每一层时间，其实有效的很少，所以用bfs取有效点更新，这样可以减少一些时间复杂度，最终跑出来1593ms
#include#include #include #include #include #include #include #include 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 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