kmjp's blog

競技プログラミング参加記です

LeetCode Biweekly Contest 135 : 3225. Maximum Score From Grid Operations

これ想定解なのか…?

問題

H*Wのグリッドが与えられる。
各マスには整数値が書かれている。

ここで一部のマスを黒く塗ることを考える。
あるマスを黒く塗る場合、その上のマスも黒く塗らないといけない。

この時、塗り方のスコアは、白マスのうち左右どちらかの隣接マスが黒いものに書かれた整数値の和とする。
スコアの最大値を求めよ。

解法

グリッドを1列ずつ見て行き、何行目まで塗るか考える。
その際、1列手前と2列手前で何行目まで塗ったかを覚えておけば、O(W*H^3)のDPとなる。
定数倍高速化をするとどうにか通る。

ll from[102][102];
ll to[102][102];
ll V[102][102];

class Solution {
public:
    long long maximumScore(vector<vector<int>>& grid) {
        int H=grid.size(),W=grid[0].size();
        int y,y1,y2,x,k;
        FOR(x,W) FOR(y,H) V[x][y+1]=V[x][y]+grid[y][x];
        
       
        FOR(y1,H+1) FOR(y2,H+1) {
			if(y1==0) from[y1][y2]=0;
			else from[y1][y2]=-1LL<<60;
		}
		
        for(x=1;x<W;x++) {
			FOR(y1,H+1) FOR(y2,H+1) to[y1][y2]=-1LL<<60;
			
			FOR(y1,H+1) FOR(y2,H+1) if(from[y1][y2]>=0) {
				if(y1<y2) {
					from[y1+1][y2]=max(from[y1+1][y2],from[y1][y2]);
					continue;
				}
				FOR(y,H+1) {
					ll a;
					if(y<=y2) a=V[x][y2]-V[x][y];
					else if(y>max(y1,y2)) a=V[x-1][y]-V[x-1][max(y1,y2)];
					
					to[y2][y]=max(to[y2][y],from[y1][y2]+a);
				}
			}
			swap(from,to);
		}
		ll ret=0;
		FOR(y1,H+1) FOR(y2,H+1) ret=max(ret,from[y1][y2]);
		return ret;
        
        
    }
};

まとめ

難易度7でもいい気はする。