LeetCode Biweekly Contest 137 : 3257. Maximum Value Sum by Placing Three Rooks II

想定解と異なるやり方だったっぽい。
https://leetcode.com/problems/maximum-value-sum-by-placing-three-rooks-ii/

問題

H*Wのグリッドが与えられる。
各セルには整数値が設定されている。

ここから3セルを選び、整数値の総和を最大化したい。
ただし、その3セルは異なる行・列になければならない。得られる総和の最大値を求めよ。

解法

3セルのうち1つは、左上か右上か左下か右下に飛び出した位置にある。
以下では右下にあるケースを考える。(他の場合も同様に総当たりする)

右下にあるセルの位置を総当たりしよう。
そうすると、そこから左上にある矩形領域から2セルを選ぶ問題と置くことができる。
これはDPであらかじめ2セルの総和の最大値を求めておけば、均しO(HW)で解ける。

ll LU2[505][505];
ll RU2[505][505];
ll LD2[505][505];
ll RD2[505][505];

class Solution {
public:
    long long maximumValueSum(vector<vector<int>>& board) {
        int H=board.size();
        int W=board[0].size();
        int y,x;
        FOR(y,H+2) FOR(x,W+2) {
			LU2[y][x]=RU2[y][x]=LD2[y][x]=RD2[y][x]=-1LL<<60;
		}
		
		ll tx[505];
		FOR(x,W+2) tx[x]=-1LL<<60;
		FOR(x,W) tx[x+1]=board[0][x];
		for(y=2;y<=H;y++) {
			ll px=tx[1];
			ll cx=board[y-1][0];
			for(x=2;x<=W;x++) {
				ll px2=tx[x];
				ll cx2=board[y-1][x-1];
				LU2[y][x]=max(px+cx2,px2+cx);
				LU2[y][x]=max(LU2[y][x],LU2[y-1][x]);
				LU2[y][x]=max(LU2[y][x],LU2[y][x-1]);
				px=max(px,px2);
				cx=max(cx,cx2);
			}
			px=tx[W];
			cx=board[y-1][W-1];
			for(x=W-1;x>=1;x--) {
				ll px2=tx[x];
				ll cx2=board[y-1][x-1];
				RU2[y][x]=max(px+cx2,px2+cx);
				RU2[y][x]=max(RU2[y][x],RU2[y-1][x]);
				RU2[y][x]=max(RU2[y][x],RU2[y][x+1]);
				px=max(px,px2);
				cx=max(cx,cx2);
			}
			FOR(x,W) tx[x+1]=max(tx[x+1],(ll)board[y-1][x]);
		}
		FOR(x,W+2) tx[x]=-1LL<<60;
		FOR(x,W) tx[x+1]=board[H-1][x];
		for(y=H-1;y>=1;y--) {
			ll px=tx[1];
			ll cx=board[y-1][0];
			for(x=2;x<=W;x++) {
				ll px2=tx[x];
				ll cx2=board[y-1][x-1];
				LD2[y][x]=max(px+cx2,px2+cx);
				LD2[y][x]=max(LD2[y][x],LD2[y+1][x]);
				LD2[y][x]=max(LD2[y][x],LD2[y][x-1]);
				px=max(px,px2);
				cx=max(cx,cx2);
			}
			px=tx[W];
			cx=board[y-1][W-1];
			for(x=W-1;x>=1;x--) {
				ll px2=tx[x];
				ll cx2=board[y-1][x-1];
				RD2[y][x]=max(px+cx2,px2+cx);
				RD2[y][x]=max(RD2[y][x],RD2[y+1][x]);
				RD2[y][x]=max(RD2[y][x],RD2[y][x+1]);
				px=max(px,px2);
				cx=max(cx,cx2);
			}
			FOR(x,W) tx[x+1]=max(tx[x+1],(ll)board[y-1][x]);
		}
		
		ll ret=-1LL<<60;
		FOR(y,H) FOR(x,W) {
			ret=max(ret,board[y][x]+LU2[y][x]);
			ret=max(ret,board[y][x]+RU2[y][x+2]);
			ret=max(ret,board[y][x]+LD2[y+2][x]);
			ret=max(ret,board[y][x]+RD2[y+2][x+2]);
			//cout<<board[y][x]<<" "<<LU2[y][x]<<" "<<RU2[y][x+2]<<" "<<LD2[y+2][x]<<" "<<RD2[y+2][x+2]<<" "<<ret<<endl;
		}
		return ret;
		
        
        
    }
};

まとめ

こんな複雑なことする必要なかったか…。