Let the light guide us
题意翻译
有一个n*m的平原,要求每行选一个点,选$n$个点建造塔楼。
平原上每个点都有他自己的花费时间和魔法值。
为了正确控制塔楼,我们必须保证连续两排的每两座塔共用一个共同的魔法区域。
也就是要求每两行相邻的点都满足如下关系:
如果第$i$行选$j$,第$i+1$行选$k$,则需$|j-k|≤f(i,j)+f(i+1,k)$。
问花费的总时间最少为多少?
输入$n,m$。
再输入两个$n*m$的矩阵。
第一个矩阵 $T[i][j] $表示的是花费时间,
第二个矩阵 $f[i][j] $表示的是魔法值。
题目描述
[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=447&page=show_problem&problem=4236
[PDF](https://uva.onlinejudge.org/external/14/p1490.pdf)