[BZOJ3437] 小P的牧場 && 斜率優化

如果你搞了前面的斜率優化的題 那麼這道題應該不算難  考的時候腦殘推錯了 說不出話來  BZOJ資料顯示也是坑 明明100W 後面加個，0 關鍵是我開1000W會直接T 坑

#include<cstdio>
using namespace std;
typedef long long LL;
const int MAXN = 1000000;
LL d[MAXN+10], Q[MAXN+10], Cost[MAXN+10], F, R, S[MAXN+10], T[MAXN+10];
int n, m;
inline LL Slope_U(int i, int j)
{
	return d[i] + T[i] - (d[j] + T[j]);
}
inline LL Slope_D(int i, int j)
{
	return S[i] - S[j];
}
inline LL read()
{     
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
	return x*f;
}
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) Cost[i] = read();
	for(int i = 1; i <= n; i++) {
		LL x = read();
		S[i] = S[i-1] + x;
		T[i] = T[i-1] + x * i;
	}
	F = R = Q[0] = 0;
	Q[R++] = 0;
	for(int i = 1; i <= n; i++)
	{
		while(F < R-1 && Slope_U(Q[F+1], Q[F]) <= Slope_D(Q[F+1], Q[F]) * i)
			F++;
		d[i] = d[Q[F]] + Cost[i] + i * (S[i] - S[Q[F]]) - (T[i] - T[Q[F]]); 
		while(F < R-1 && Slope_U(Q[R-1], Q[R-2]) * Slope_D(i, Q[R-1]) >= Slope_U(i, Q[R-1]) * Slope_D(Q[R-1], Q[R-2]))
			R--;
		Q[R++] = i;
	}
	printf("%lld\n", d[n]);
}

/*
4
2 4 2 4
3 1 4  2
*/