これが最大って証明可能なのかな?
https://yukicoder.me/problems/no/540
問題
矩形領域(0,0)-(W,H)中の格子点(W+1)*(H+1)個を考える。
距離1内の各格子点を線分で結び、全格子点を通るパスを作るとき、線分の数を最大化せよ。
解法
H,Wの偶奇で場合分けする。
図はEditorialを見てもらった方がいいのでここでは方針だけ示す。
- H,Wがともに偶数の時
- 外側から2列ずつ削り取るように渦巻き状に内側に向けて移動していく。最後は長めの線分が残る可能性がある。
- それ以外の場合
- 端から2列ずつ削り取るように移動していく。列を削るか行を削るかはW,Hのうち奇数がどちらかによって選ぶ。ともに奇数の場合小さい方を選ぶ。
ll W,H; void solve() { int i,j,k,l,r,x,y; string s; cin>>H>>W; ll ret=0; if(H%2 + W%2 == 0) { while(H&&W) { ret += 2*(W+H-1); W-=2; H-=2; } if(H||W) ret++; } else if(H%2 + W%2 == 1) { ret = (W+1)*(H+1) - ((H%2)?H:W); } else if(H%2 + W%2 == 2) { ret = (W+1)*(H+1) - min(H,W); } cout<<ret<<endl; }
まとめ
コード長からDP等ではないとは思ったけど…。
2列ずつ削るのは思いついたけど、渦巻き状が最小か自身を持ちきれなかった。