题目

题目描述

Jesseliu喜欢购物（是的千真万确！），他（？？？）尤其喜欢那种横扫一片商店的快感（？？？）
最近，他打算对南门口的商店实行他疯狂的购物计划
南门口的商业区中最繁华的就是黄兴路步行街了
这条街上有$n$个商店，Jesseliu打算进攻$m$次，每次扫荡第$[l_i,r_i]$个商店
Jesseliu会把他经过的每个商店扫荡一空(换句话说,就是一个商店不会被算两次)
因为连续地扫一片商店是很爽的（？？？），所以Jesseliu把一次扫荡的$happy$值定义为所有连续的一段没被扫空的商店$happy$值之和的平方的和，已被扫空的不再计算
现在你不经意间得知了Jesseliu的购物计划（？？？），而你需要将这些计划排序并求出Jesseliu最多获得的$happy$值之和，如果算错了Jesseliu就会卖萌，这可是很致命的哦！（？？？）

输入格式

第一行为$n$和$m$，意义如描述之所示
接下来一行$n$个数，第$i$个数表示第$i$个商店的$happy$值
接下来$m$行，每行两个数
$l_i,r_i$表示Jesseliu第$i$次行动要扫荡第$l_i$到第$r_i$个商店

输出格式

一行,包含一个数即为Jesseliu最多获得的$happy$值之和

样例

样例输入

14 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1
4 9
2 12

样例输出

数据范围与提示

对于$30 \%$的数据，$n \leqslant 10,m \leqslant 8$
对于$60 \%$的数据，$n \leqslant 1000,m \leqslant 1000$
对于$100 \%$的数据，$n \leqslant 5000,m \leqslant 10^6,happy$值$\leqslant 100$

题解

显然，这是一个DP
我们假设$f_i$表示前$i$个的最大值（如果有的区间$[l,r]$满足$l\leqslant i

#include<algorithm>
#include<cstdio>
using namespace std;
int n,m,ans,h[5010],s[5010],l[1000010],r[1000010],R[5010],f[5010];
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",&h[i]),s[i]=s[i-1]+h[i];
    for(int i=1;i<=m;i++) scanf("%d%d",&l[i],&r[i]);
    for(int i=1;i<=m;i++) R[l[i]]=max(R[l[i]],r[i]);
    for(int i=1;i<=n;i++) R[i]=max(R[i],R[i-1]);
    for(int i=1;i<=n;i++) for(int j=i;j<=R[i];j++) f[j]=max(f[j],f[i-1]+(s[j]-s[i-1])*(s[j]-s[i-1]));
    for(int i=1;i<=n;i++) ans=max(ans,f[i]);
    printf("%d",ans);
}