コンテスト後のツイート
F あるマスが黒だとその下のマスも黒い。ので、列ごとに見ると「xマスより下が黒」という状態で表せる。これを状態としてDP。
— titia (@titia_til) July 22, 2023
G - One More Grid Task
解説AC。
「最大長方形」のアルゴリズムを使うのかな、とはコンテスト中に考えたのに、（検索したら）最大長方形のアルゴリズムはヒストグラムの形にしか適応できないことを見て、この問題には適応できないと思ってしまった。
「i行より上の部分だけを見る」として最大長方形のアルゴリズムを適応する発想がなかった。
最大長方形のアルゴリズムを使うかもしれないと思ったのなら、もうちょっと使える形に変形できないか考えないと。
0 件のコメント:
コメントを投稿