紫书 习题 8-24 UVa 10366 （构造法）

又是一道非常复杂的构造法……

#include<cstdio>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 1123;

int L, R, LHs[MAXN], RHs[MAXN], LH, RH, LHi, RHi;

int solve()

{

	int lt = 0, rt = 0, t;

	for(int i = L, h = LHs[L]; i > LHi; i--) //从最高隔板到边缘的时间

		lt += h, h = max(h, LHs[i-1]);

	for(int i = R, h = RHs[R]; i > RHi; i--)

		rt += h, h = max(h, RHs[i-1]);

	if(LH == RH) return (LHi + RHi + 1) * LH + min(lt, rt) * 2; //小细节， 矩形宽要加1， 拿样例算一下就知道了

	int T = min(LH, RH), LTi = 0, RTi = 0;

	while(LTi < L && LHs[LTi] < T) LTi++;

	while(RTi < R && RHs[RTi] < T) RTi++;

	if(LH < RH)

	{

		rt = 0;

		for(int i = RTi, h = T; RHs[i] <= T; i++)

			rt += h, h = max(RHs[i+1], h);

		t =  lt > rt ? (lt + rt) : 2 * lt;

	}

	if(LH > RH)

	{

		lt = 0;

		for(int i = LTi, h = T; LHs[i] <= T; i++)

			lt += h, h = max(LHs[i+1], h);

		t =  rt > lt ? (lt + rt) : 2 * rt;

	}

	return t + (RTi + LTi + 1) * T;

}

int main()

{

	int lx, rx;

	while(scanf("%d%d", &lx, &rx) && lx && rx)

	{

		LH = RH = 0;

		L = (-lx) / 2, R = rx / 2;

		for(int i = lx; i < 0; i += 2)

		{

			int j = (-i) / 2; scanf("%d", &LHs[j]);

			if(LH <= LHs[j]) LH = LHs[j], LHi = j;

		}

		for(int i = 1; i <= rx; i += 2)

		{

			int j = i / 2; scanf("%d", &RHs[j]);

			if(RH < RHs[j]) RH = RHs[j], RHi = j;

		}

		printf("%d\n", solve() * 2); //开始除以2， 后来乘回去

	}

	return 0;

}