简要题意
\(n\le 10^3 , \sum K_i\le3\times10^5\)
思路
首先容易想到一个暴力DP，\(f_{l,r,x}\) 表示区间中最大值为 \(x\) 的最大值
稍微想亿下可以发现如果这个位置选的不是区间最大值的话，答案一定不优
所以我们可以直接 \(f_{l,r}\) DP转移，但复杂度还是没变，我们把柿子列出来
\(f_{l,r}=max_{p\in[l,r]}(f_{l,p-1}+f_{p+1,r}+V_{p,k}*sum-C_{p,k})\)
发现这个函数是凸的，于是我们考虑斜率优化，然后改变枚举顺序，再然后就做完了
code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 1005
#define M 300005
int n,top,m;
int Q[N][N],cnt[N][N],sum[N][N],f[N][N];
struct A{
int x,y;
}d[M],q[M];
vector<A> g[N];
bool cmp(A a,A b){
if(a.x!=b.x) return a.x<b.x;
return a.y<b.y;
}
int xiao(A a,A b,A c,A d){
return (__int128)(b.y-a.y)*(d.x-c.x)<(__int128)(d.y-c.y)*(b.x-a.x);
}
void add(A p){
if(p.x==q[top].x) return ;
while(top>1&&xiao(q[top],p,q[top-1],q[top])) top--;
q[++top]=p;
}
int cal(int k,int x,int y){
return k*x-y;
}
signed main(){
freopen("war.in","r",stdin);
freopen("war.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
scanf("%lld",&Q[i][j]);
cnt[i][j]=cnt[i-1][j]+Q[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++) sum[i][j]=sum[i][j-1]+cnt[j][j]-cnt[i-1][j];
}
for(int i=1;i<=n;i++){
scanf("%lld",&m);
for(int j=1;j<=m;j++) scanf("%lld%lld",&d[j].x,&d[j].y);
sort(d+1,d+1+m,cmp);top=0;
for(int j=1;j<=m;j++) add(d[j]);
for(int j=1;j<=top;j++) g[i].push_back(q[j]);
}
memset(f,-127,sizeof(f));
for(int i=0;i<=n;i++) f[i+1][i]=0;
for(int l=n;l>=1;l--){
for(int p=l;p<=n;p++){
int i=0;
for(int r=l;r<=n;r++){
int he=sum[l][r]-sum[l][p-1]-sum[p+1][r];
while(i<g[p].size()-1&&cal(he,g[p][i].x,g[p][i].y)<cal(he,g[p][i+1].x,g[p][i+1].y)) i++;
f[l][r]=max(f[l][r],f[l][p-1]+f[p+1][r]+cal(he,g[p][i].x,g[p][i].y));
}
}
}
printf("%lld\n",f[1][n]);
return 0;
}