1.11模拟赛 T1题解

简要题意

\(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;
}