TopCoder SRM 797 : Div1 Easy FlightPlan

Medium解けない病継続中…。
https://community.topcoder.com/stat?c=problem_statement&pm=16756&rd=18435

問題

H*Wのグリッドがあり、各マスはそれぞれある高さの直方体が置かれている。
水平方向に距離1移動にかかるコストと、上下方向に距離1移動するコストが与えられる。
(0,0)の直方体の上の中心から、(H-1,W-1)の直方体の上の中心に直方体内を通らずに移動する最小コストを求めよ。

解法

以下の2通りでいずれも可能。前者の方がダイクストラでlogがかかる分TLEが怖いが、なんとか通る。

• 高さを座標圧縮すれば、O(H^2*W^2)頂点のダイクストラに持ち込める。
• 通る最大の高さをHW通り総当たりしよう。個々のループではBFSでO(HW)で解けるので、O(H^2*W^2)で解ける。

int Z[50][50];
ll dp[50][50][2500];

class FlightPlan {
	public:
	long long fly(int R, int C, vector <int> H, int cup, int cdn, int clr) {
		vector<ll> Y;
		FORR(h,H) Y.push_back(h);
		sort(ALL(Y));
		Y.erase(unique(ALL(Y)),Y.end());
		int y,x,z;
		FOR(y,R) FOR(x,C) {
			FOR(z,R*C) dp[y][x][z]=1LL<<60;
			Z[y][x]=lower_bound(ALL(Y),H[y*C+x])-Y.begin();
		}
		dp[0][0][Z[0][0]]=0;
		priority_queue<pair<ll,int>> Q;
		Q.push({0,Z[0][0]*2500});
		while(Q.size()) {
			ll co=-Q.top().first;
			int cy=Q.top().second%2500/50;
			int cx=Q.top().second%2500%50;
			int ct=Q.top().second/2500;
			Q.pop();
			if(dp[cy][cx][ct]!=co) continue;
			int dy[]={1,-1,0,0,0,0};
			int dx[]={0,0,1,-1,0,0};
			int dt[]={0,0,0,0,1,-1};
			int i;
			FOR(i,6) {
				int ty=cy+dy[i];
				int tx=cx+dx[i];
				int tt=ct+dt[i];
				if(ty<0||ty>=R||tx<0||tx>=C) continue;
				if(tt<Z[ty][tx]||tt>=Y.size()) continue;
				ll nco=co;
				if(dt[i]==-1) nco+=cdn*(Y[ct]-Y[tt]);
				if(dt[i]==1) nco+=cup*(Y[tt]-Y[ct]);
				if(dt[i]==0) nco+=clr;
				if(dp[ty][tx][tt]>nco) {
					dp[ty][tx][tt]=nco;
					Q.push({-nco,tt*2500+ty*50+tx});
				}
			}
			
		}
		return dp[R-1][C-1][Z[R-1][C-1]];
	}
}

まとめ

意外にsystest落ちてたね。