TobiasGSmollett https://blog.hatena.ne.jp/TobiasGSmollett/ tobiasの日記 https://tobiasgsmollett.hatenadiary.org/ AOJ 動的計画法 問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0089 動的計画法で解いた。 dp[ i行目 ][ j列目 ]:=最大コストとすると、i行目のj列目にはi-1行目の同じj列と i i>N のとき i-1行目のj+1列目 (Nは行数) から来れるので、この2ヶ所までのパスの最大コスト+i行j列の値 という式で計算できる。 #include<iostream> #include<vector> #include<algorithm> #include<string> using namespace std; int mai… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftobiasgsmollett.hatenadiary.org%2Fentry%2F20130602%2F1370175981" title="0089:The Shortest Path on A Rhombic Path - tobiasの日記" 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-06-02 21:26:21 rich https://tobiasgsmollett.hatenadiary.org/entry/20130602/1370175981 1.0 100%