斜率优化的模板题

给出n个数以及M，你可以将这些数划分成几个区间，每个区间的值是里面数的和的平方+M，问所有区间值总和最小是多少。

如果不考虑平方，那么我们显然可以使用队列维护单调性，优化DP的线性方法来做，但是该题要求的是区间和的平方，于是要转换单调的计算方法为斜率，也就是凸线。

其他就是最基本的单调DP

/** @Date    : 2017-09-04 15:39:05

  * @FileName: HDU 3507 单调队列 斜率优化 DP.cpp

  * @Platform: Windows

  * @Author  : Lweleth (SoungEarlf@gmail.com)

  * @Link    : https://github.com/

  * @Version : $Id$

  */

#include <bits/stdc++.h>

#define LL long long

#define PII pair<int ,int>

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5+20;

const double eps = 1e-8;

int n, m;

int a[5*N];

LL dp[5*N];

LL sum[5*N];

LL XX(int a, int b)

{

	return dp[b] + sum[b] * sum[b] - (dp[a] + sum[a] * sum[a]);

}

LL YY(int a, int b)

{

	return 2 * (sum[b] - sum[a]);

}

int main()

{

	while(~scanf("%d%d", &n, &m))

	{

		MMF(sum);

		MMF(dp);

		for(int i = 1; i <= n; i++)

		{

			scanf("%d", a + i);

			sum[i] = sum[i - 1] + a[i];

		}

		deque<int>q;

		q.push_back(0);

		for(int i = 1; i <= n; i++)

		{

			auto pos = q.begin();

			while(q.size() > 1 && XX(*pos, *(pos + 1)) <= sum[i] * YY(*pos, *(pos + 1)))

				q.pop_front(), pos = q.begin();

			if(!q.empty())

				dp[i] = dp[q.front()] + (sum[i] - sum[q.front()])*(sum[i] - sum[q.front()]) + m;

			//cout << dp[i] << endl;

			pos = q.end();

			while(q.size() > 1 && XX(*(pos - 2), *(pos - 1)) * YY(*(pos - 1), i) >= XX(*(pos - 1), i) * YY(*(pos - 2), *(pos - 1)))

			{

				q.pop_back();

				pos = q.end();

			}

			q.push_back(i);

		}

		printf("%lld\n", dp[n]);

	}

    return 0;

}