Ural 1029 Ministry 题解
题意
给定一个$n\times m(1\le n \le10,1\le m \le500)$的矩阵,矩阵中的每个值都是一个小于等于$10^9$的正整数。
现在从第$1$行的任意位置开始,在第$n$行的任意位置结束。每次有$3$种移动选择(不能移动到矩阵外)。
设当前位置为$(i,j)$
移动到$(i+1,j)$
移动到$(i,j-1)$
移动到$(i,j+1)$
每条路径的价值是路径走过所有的位置上的值的和(小于等于$10^9$)。
问在所有路径中,路径价值最小的,输出这条路径所有位置的列号。
题解
考虑记忆化搜索(DP也可以)。
对于每个点,记忆化搜索可以移动到它的$3$种位置,取最小值即可,顺便记录一下路径。
也可以无脑最短路。
Tips:
WA$1$的同学不要着急,Test$1$并不是样例,仔细找找有没有错误。
设$(i,j)$的答案为$dp(i,j)$,矩阵中的值为$a(i,j)$,状态转移方程如果是$dp(i,j)=\min\{dp(i-1,j),dp(i,j-1),dp(i,j+1) \}+a(i,j)$可能会WA$1$,改为$dp(i,j)=\min\{dp(i-1,j)+a(i,j),dp(i,j-1)+a(i,j),dp(i,j+1)+a(i,j) \}$即可AC。目前并不知道原因(我太弱了),如果有知道的可以在评论区留言,谢谢!
程序
AC程序
1 | // #pragma GCC optimize(2) |
WA$1$程序
1 | // #pragma GCC optimize(2) |