モバイルBOJ 11048

6798 ワード
2021.03.28 テキストリンク
https://www.acmicpc.net/problem/11048
1秒、256 MBメモリ
input :
  • N, M(1 ≤ N, M ≤ 1,000)
  • (r,c)に置かれたキャンディの個数.(0<=キャンディ個数<=100)
    • output :
  • (N,M)に移動すると、導入可能なキャンディ数出力
    • が出力.
    条件:
  • ジュンギュは現在(1,1)、(N,M)に移動する準備をしています.
  • ジュンギュは(r,c)、(r+1,c),(r,c++1),(r+1,c++1)に移動でき、(r+1,c++1)訪問するたびに部屋に置いてあるキャンディを部屋ごとに持ち去ることができます.そして、迷宮から出られない.
    • 当初,BFSを用いてdp配列中に各キャンディの最大数を格納しようとした.しかし
    2 2
    0 0
    0 5
    この場合graph[nx][ny]+dp[x]>=dp[nx][ny]にもqを追加するとタイムアウトが発生する...
    だから.DPに行こう
    まず...対角線に移動した場合は削除できます.
    対角線に移動するよりも右->下に移動する方が期待値が大きいからです.
    だからdpの点火式は以下の通りです.
    dp[i][j] = graph[i - 1][j - 1] + max(dp[i - 1][j], dp[i][j - 1])
    そして、dp[n][m]の値を出力する.
    import sys

n, m = map(int, sys.stdin.readline().split())
graph = []
for i in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))

dp = [[0] * (m + 1) for i in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, m + 1):
        dp[i][j] = graph[i - 1][j - 1] + max(dp[i - 1][j], dp[i][j - 1])
print(dp[n][m])
    クッキーとデータ応答の問題
    [BOJ]3190ヘビ-サムスンソフトウェア能力試験機