Description：

有一排 $n$ 个数字和 $m$ 个区间，每次从这些区间中选一个并获得他们中连续段的和的平方的和，并把这些数删去，选一个选区间的顺序最大化最终结果的和。

$1\le n \le 5000,1\le m \le1000000$

Solution：

由于平方的和小于等于和的平方，每次操作一定是选取了一段，所以区间包含的情况只要保存较大的就可以了，这样会剩下 $O(n)$ 个区间，因为每个右端点最多只会对应一个区间，然后 $O(nm')$ 预处理出每个位置最靠左可以扩展到什么位置，也就是说最靠左的满足有一个区间包含这一段的位置 $lef[i]$ ，然后就可以 $DP$ 了，所有在 $[lef[i]-1,i)$ 这个范围内的状态都能转移，转移方程为 $f[i]=max(f[j]+(sum[i]-sum[j])^2,f[i-1])$ 。

时间复杂度 $O(n^2)$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 5010

#define MAXM 1000010

int val[MAXN],sum[MAXN];

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

struct opt

{

	int l,r;

	bool tag;

	opt(){tag = true;}

}s[MAXM],a[MAXN];

int tot = 0;

bool cmp_r(opt a,opt b){return (a.r == b.r ? a.l > b.l : a.r < b.r);}

int lef[MAXN];

int f[MAXN];

int main()

{

	freopen("shopping.in","r",stdin);

	freopen("shopping.out","w",stdout);

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d",&val[i]);

	for(int i = 1;i <= n;++i)sum[i] = sum[i - 1] + val[i];

	for(int i = 1;i <= m;++i)s[i].l = read(),s[i].r = read();

	sort(s + 1,s + 1 + m,cmp_r);

	for(int i = 2;i <= m;++i)

		if(s[i].r == s[i - 1].r)

			s[i - 1].tag = false;

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

		if(s[i].tag)a[++tot] = s[i];

	memset(lef,0x3f,sizeof(lef));

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

		for(int j = a[i].l;j <= a[i].r;++j)

			lef[j] = min(lef[j],a[i].l);

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

	{

		f[i] = f[i - 1];

		for(int j = lef[i] - 1;j < i;++j)

		{

			f[i] = max(f[i],f[j] + (sum[i] - sum[j]) * (sum[i] - sum[j]));

		}

	}

	cout << f[n] << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}