2013 TCO Round2C 550 TheMountain

2013-05-12

17:06 |

WxH の表 g の一部が与えられる。0≦tx＜W, 0≦ty＜H のどこかに頂上(tx, ty) を決めてそこが頂上になるよう他のマスを決めたい。
（0≦x＜tx なら g[y][x]＜g[y][x+1], tx≦x＜W なら g[y][x]＞g[y][x+1]）
（0≦y＜ty なら g[y][x]＜g[y+1][x], ty≦y＜H なら g[y][x]＞g[y+1][x]）
どこかが頂上になるような時の表の数字の合計値の最小値を求める問題。
W, H≦200, 与えられる数字≦1000

250 で Warshall-Floyd を書いて満足してしまった dist-1 勢だったので時間がある
が、Naive解を書いた所で終了

（あとで）

頂上の場所によらず、頂上より左上にあるエリアは左上から単調増加になるように決めていけばいいので最初に1回だけ累積和を求めておく
右上、左下、右下も同じ。
頂上の場所の候補それぞれについて
尾根のところ(tx==x || ty==y)の数値を決める（左右/上下から上がってきたやつの最大値）
尾根の合計とそれ以外の左上、右上、左下、右下部分の累積和を合計

本番でミスなしで書ける気がしなし

(accepted in practice room)

#define INF (1LL<<30)

class TheMountain {
	public:
	int minSum(int H, int W, vector <int> IY, vector <int> IX, vector <int> IE) {
		int ans=INF;
		VVI init(H+2, VI(W+2, 0));
		VVI w[4];
		REP(i, 4) w[i] = init;
		REP(i, IY.size()) init[IY[i]+1][IX[i]+1] = IE[i];
		VVI dp[4];
		REP(i, 4) dp[i] = VVI(H+2, VI(W+2, 0));
		int sx[] = {0, W-1, 0, W-1};
		int sy[] = {0, 0, H-1, H-1};
		int dx[] = {1, -1, 1, -1};
		int dy[] = {1, 1, -1, -1};
		REP(dir, 4) {
			int Dx = dx[dir];
			int Dy = dy[dir];
			for(int y=sy[dir]; 0<=y && y<H; y+=Dy) for(int x=sx[dir]; 0<=x && x<W; x+=Dx) {
				w[dir][y +1][x +1] = -1;
				int v = max(init[y+1][x+1], max(w[dir][y +1][x-Dx +1], w[dir][y-Dy +1][x +1])+1);
				if((w[dir][y +1][x-Dx +1]!=-1 && w[dir][y-Dy +1][x +1]!=-1) && (init[y+1][x+1]==0 || init[y+1][x+1] == v)) {
					w[dir][y +1][x +1] = v;
				}
				
				dp[dir][y +1][x +1] = -1;
				int py = dp[dir][y-Dy +1][x +1];
				int px = dp[dir][y +1][x-Dx +1];
				int pxy = dp[dir][y-Dy +1][x-Dx +1];
				if(!(w[dir][y +1][x +1]==-1 || px==-1 || py==-1 || pxy==-1)) {
					dp[dir][y +1][x +1] = w[dir][y +1][x +1] + py + px - pxy;
				}
			}
		}
		REP(ty, H) REP(tx, W) {
			VI wx(W), wy(H);
			int ok=1;
			RANGE(x, 0, tx+1) { int a=w[0][ty+1][x+1], b=w[2][ty+1][x+1]; wx[x]=max(wx[x], max(a, b)); if(min(a, b)==-1) ok=0; }
			RANGE(x, tx, W)   { int a=w[1][ty+1][x+1], b=w[3][ty+1][x+1]; wx[x]=max(wx[x], max(a, b)); if(min(a, b)==-1) ok=0; }
			RANGE(y, 0, ty+1) { int a=w[0][y+1][tx+1], b=w[1][y+1][tx+1]; wy[y]=max(wy[y], max(a, b)); if(min(a, b)==-1) ok=0; }
			RANGE(y, ty, H)   { int a=w[2][y+1][tx+1], b=w[3][y+1][tx+1]; wy[y]=max(wy[y], max(a, b)); if(min(a, b)==-1) ok=0; }
			if(!ok) continue;
			
			int wx_sum=0, wy_sum=0;
			REP(x, W) wx_sum += wx[x];
			REP(y, H) wy_sum += wy[y];
			int wxy = wx_sum + wy_sum - min(wx[tx], wy[ty]);
			
			int v0 = dp[0][ty-1 +1][tx-1 +1];
			int v1 = dp[1][ty-1 +1][tx+1 +1];
			int v2 = dp[2][ty+1 +1][tx-1 +1];
			int v3 = dp[3][ty+1 +1][tx+1 +1];
			if(v0==-1 || v1==-1 || v2==-1 || v3==-1) continue;
			int v4 = v0+v1+v2+v3;
			int lans = wxy + v4;
			ans = min(ans, lans);
		}
		return ans==INF ? -1 : ans;
	}
};