用递归求最高点的漫水时间,应该算法上没有错吧?


#include<stdio.h>

__int64 MF[100000];				//MF为过水时间

class myclass {
public:
    myclass(__int64 a = 0, __int64 b = 0):first(a), second(b){}
    __int64 first;
    __int64 second;
	void operator = (const myclass &m){
		first = m.first;
		second = m.second;
	}
};
myclass my[100000];

void op(__int64 l, __int64 r, __int64 FP, __int64 add){	//FP主注水位置, add为要加的权值
	__int64 j, tmax, max, mh, AD, ADh;
	for(j = tmax = l, max = 0; j <= r; j++){
		if(max < my[j].second){
			max = my[j].second;
			tmax = j;
		}
	}

	for(MF[tmax] = add, j = l, mh = my[tmax].second+1; j <= r; j++)
		MF[tmax] += (mh-my[j].second)*my[j].first;
	
	if(FP == tmax)
		;
	else if(FP < tmax){
		op(l, tmax-1, FP, add);
		for(AD = 0, ADh = my[tmax].second, j = l; j < tmax; j++){
			AD += (ADh-my[j].second)*my[j].first;
		}
		if(tmax < r)
			op(tmax+1, r, tmax+1, add+AD);
	}
	else{
		op(tmax+1, r, FP, add);
		for(AD = 0, ADh = my[tmax].second, j = tmax+1; j <= r; j++)
			AD += (ADh-my[j].second)*my[j].first;
		if(tmax > l)
			op(l, tmax-1, tmax-1, add+AD);
	}
}

int main(void){
	__int64 n, j, w, h, tmin, min = 1000000;
	scanf("%I64d", &n);
	for(j = 0, tmin = 0; j < n; j++){
		scanf("%I64d %I64d", &w, &h);
		if(h < min){
			min = h;
			tmin = j;
		}
		my[j] = myclass(w, h);
	}

	op(0, n-1, tmin, 0);

	for(j = 0; j < n; j++)
		printf("%I64d\n", MF[j]);
	return 0;
}