Codeforces #642 : Div3. F. Decreasing Heights

この回はだいぶすんなり。
https://codeforces.com/contest/1353/problem/F

問題

H*Wのグリッドが与えられ、それぞれ値A[r][c]が与えられる。
左上のセルから、右または下に移動することを繰り返し、右下セルに移動したい。
その際、

• 移動元と移動先の値は、移動先の方が1大きくなければならない。
• 事前にA[r][c]の値は任意の非負整数だけデクリメントできる。

右下に移動できる最小の総デクリメント回数を求めよ。

解法

B[r][c]=A[r][c]-r-cとするBを考えると、前者の条件は「移動元と移動先の値は等しくなければならない」となる。
通るマスの最小値を総当たりし、DPで右下マスに至る最小総デクリメント数を求めて行けば、O(H^2*W^2)で処理できる。

int T,H,W;
ll A[101][101];
ll D[101][101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>H>>W;
		FOR(y,H) FOR(x,W) {
			cin>>A[y][x];
			A[y][x]-=y+x;
		}
		
		ll ret=1LL<<60;
		FOR(i,H) FOR(j,W) {
			ll C=A[i][j];
			FOR(y,H) FOR(x,W) D[y][x]=1LL<<60;
			D[0][0]=0;
			FOR(y,H) FOR(x,W) {
				if(C>A[y][x]) {
					D[y][x]=1LL<<60;
					continue;
				}
				D[y][x]+=A[y][x]-C;
				if(y+1<H) D[y+1][x]=min(D[y+1][x],D[y][x]);
				if(x+1<W) D[y][x+1]=min(D[y][x+1],D[y][x]);
			}
			ret=min(ret,D[H-1][W-1]);
			
		}
		cout<<ret<<endl;
		
	}
}

まとめ

前回のDiv3はちょっと難しかったけど、また簡単に戻った。