moistx https://blog.hatena.ne.jp/moistx/ Logfiles https://logfiles.hatenablog.com/ AOJ 解いてる途中のメモ MAPの中で数字のものだけを使って文字列結合をしていく。dpはstringの配列(vector) でもつとよい。 dp[i+1][j+1] = max(dp[i][j+1]+M[i+1][j+1], max(dp[i+1][j]+M[i+1][j+1])) Mが数値か文字かの判定が必要。数値なら、数が大きくなるように追加、つまり「サイズ大順→辞書大順」で決定できる。 Mが文字なら更新はしない。解を更新するときは文字列の先頭のゼロを消して更新することを忘れない。 左上から処理していく場合はdp配列上で逐次先頭の0を弾くようにした方が良いと思う 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Flogfiles.hatenablog.com%2Fentry%2F20131116%2F1384608002" title="AOJ 1126 The Secret Number - Logfiles" 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-16 22:20:02 rich https://logfiles.hatenablog.com/entry/20131116/1384608002 1.0 100%