又是一道非常复杂的构造法……
#include#include #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; }