tei3344 https://blog.hatena.ne.jp/tei3344/ 土下座しながら探索中 https://ncastar.hatenablog.com/ UVa 動的計画法 問題リンク：Maximum Sum問題概要： N*Nの2次元配列が与えられる この中から作れる長方形のうちその要素の和が最大のものをみつけよ解法： よくあるDP memo[y][x] := memo[y-1][x] + memo[y][x-1] - memo[y+1][x+1] + array[y][x]という配列を用意する arrayは入力で与えられる2次元配列 memoは(0,0)から(x,y)までの長方形の要素の和を表す後は長方形の左上と右下をループで決めて、memoを以下の様に利用して面積を求める 左上を(x1,y1),右下を(x2,y2)とする この長方形の要素の和をSとする S =… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fncastar.hatenablog.com%2Fentry%2F20131122%2F1385136232" title=" UVa 108 : Maximum Sum - 土下座しながら探索中" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2013-11-22 01:03:52 rich https://ncastar.hatenablog.com/entry/20131122/1385136232 1.0 100%