ACM大牛，小牛，神牛帮忙看一道题吧（等我有分了再多加点，现在就这点了）
发布网友
发布时间：2022-05-06 04:06
共1个回答
热心网友
时间：2023-10-03 10:02
if( j!=n && map[j+1][k] != '#')
maxi = max2(T[j+1][k][i+1], maxi);
....
T[j][k][i] += maxi;
j是从小到大的,所以在决策T[j][k][i] 的时候用到了T[j+1][k][i+1], 显然有问题
个人感觉此题是图论的问题
首先对于一个图来说最多m*n个节点.(n*m<=100，包括了'X'和老鼠)
首先我们可以先bfs,得到任何2个节点之间的最短距离.
然后得到了一对关系，显然bfs的复杂度最多为O(n*m*n*m)=O(10000)
于是我们再枚举任意2个节点,如果他们的最短距离<=他们的时间差(可以认为'X'点时间为0),那么建边，于是问题转化为一个有向图上求最长路，可以按照拓扑顺序DP
因为猫可以停下来不走，所以i->j的充分条件显然就是i->j的最短路必须<=时间差才能到达....个人感觉~
