c081: $A.$$Town$ $traveler$
Tags : DP
Accepted rate : 1人/2人 ( 50% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-06-10 20:41

Content

在某個國家,為了讓所有城市排列整齊,政府將所有城市以$m$行$n$列的矩陣方式排列,且為了省錢只建造了左-右、上-下、左上-右下,三種方向的道路。

現在有一個商人從第$0$行第$0$列的城市出發,在不同城市及道路上進行交易,且每次皆只會走向右、下、右下三個方向的道路。

已知:

在第$i$行$j$列的城市可以賺取$p_{i,j}$的錢

在第$i$行$j$列城市通往右方城市的道路上可以賺取$a_{i,j}$的錢

在第$i$行$j$列城市通往下方城市的道路上可以賺取$b_{i,j}$的錢

在第$i$行$j$列城市通往右下方城市的道路上可以賺取$c_{i,j}$的錢

且某些道路因為法令關係而無法通過,請問此商人在抵達第$m$行$n$列的城市前最多可以賺取多少錢

 
 
Input

第一行有兩個正整數,分別代表$m$, $n$

接下來有$m*n$行,每行有四個正整數,分別代表第$i$行第$j$列的$p_{i,j}$、$a_{i,j}$、$b_{i,j}$、$c_{i,j}$($0 <= i < m$,$0 <= j < n$,以$(0, 0), (0, 1), (0, 2), ..., (m-1. n-1)$的順序排列),若該道路無法通過則輸入-1。

Output

輸出商人最多可以賺取多少錢

Sample Input #1
2 3
1 7 3 -1
5 10 8 2
4 -1 -1 -1
4 5 -1 -1
3 4 -1 -1
2 -1 -1 -1
Sample Output #1
30
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (5%): 1.0s , <1M
公開 測資點#1 (5%): 1.0s , <1M
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <10M
公開 測資點#5 (5%): 1.0s , <50M
公開 測資點#6 (5%): 1.0s , <10M
公開 測資點#7 (5%): 1.0s , <1M
公開 測資點#8 (5%): 1.0s , <10M
公開 測資點#9 (5%): 1.0s , <10M
公開 測資點#10 (5%): 1.0s , <10M
公開 測資點#11 (5%): 1.0s , <50M
公開 測資點#12 (5%): 1.0s , <10M
公開 測資點#13 (5%): 1.0s , <10M
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#15 (5%): 1.0s , <10M
公開 測資點#16 (5%): 1.0s , <50M
公開 測資點#17 (5%): 1.0s , <50M
公開 測資點#18 (5%): 1.0s , <10M
公開 測資點#19 (5%): 1.0s , <50M
Hint :

BFS?還是其實有其他方法

Tags:
DP
出處:
[管理者:
TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」