[Usaco2007 China]The Bovine Accordion and Banjo Orchestra 音乐会

音乐会"/>

[Usaco2007 China]The Bovine Accordion and Banjo Orchestra 音乐会

设 F[i][j] F [ i ] [ j ] $F[i][j]$表示手风琴手匹配到第 i i $i$个，班卓琴手匹配到第j" role="presentation" style="position: relative;">jj$j$个的最大收益。
F[i][j]=F[k][l]+A[i]×B[j]−(s[i−1]−s[k])2−(S[j−1]−S[l])2 F [ i ] [ j ] = F [ k ] [ l ] + A [ i ] × B [ j ] − ( s [ i − 1 ] − s [ k ] ) 2 − ( S [ j − 1 ] − S [ l ] ) 2 $F[i][j]=F[k][l]+A[i]\times B[j]-(s[i-1]-s[k])^2-(S[j-1]-S[l])^2$
F[i][j] F [ i ] [ j ] $F[i][j]$只能从 F[i−1][k] F [ i − 1 ] [ k ] $F[i-1][k]$和 F[k][j−1] F [ k ] [ j − 1 ] $F[k][j-1]$转移，因为如果从其他转移，可以选 a[i−1] a [ i − 1 ] $a[i-1]$和 b[j−1] b [ j − 1 ] $b[j-1]$配对，答案更优。
搞一个二维的斜率优化就好了。

#include<bits/stdc++.h>
#define il inline
#define ll long long
#define y(k) (S[k]*S[k]-f[i-1][k])
#define x(k) (S[k])
#define Y(k) (s[k]*s[k]-f[k][j-1])
#define X(k) (s[k])
#define N 1005
using namespace std;
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
il int read(){int x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=(x+(x<<2)<<1)+c-48;return x*f;
}
ll a[N],b[N],q[N][N],Q[N][N],s[N],S[N],h[N],H[N],t[N],T[N];
ll f[N][N],ans=-(1ll<<62),n;
int main(){n=read();for(int i=1;i<=n;++i) a[i]=read(),s[i]=s[i-1]+a[i];for(int i=1;i<=n;++i) b[i]=read(),S[i]=S[i-1]+b[i];for(int i=1;i<=n;++i) h[i]=H[i]=1,f[i][0]=-s[i]*s[i],f[0][i]=-S[i]*S[i];for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){f[i][j]=-s[i-1]*s[i-1]-S[j-1]*S[j-1]+a[i]*b[j];while(h[i]<t[i]&&(y(q[h[i]+1][i])-y(q[h[i]][i]))<=(x(q[h[i]+1][i])-x(q[h[i]][i]))*2*S[j-1]) ++h[i];if(i>1) f[i][j]=max(f[i][j],f[i-1][q[h[i]][i]]+a[i]*b[j]-(S[j-1]-S[q[h[i]][i]])*(S[j-1]-S[q[h[i]][i]]));while(h[i]<t[i]&&(y(q[t[i]][i])-y(q[t[i]-1][i]))*(x(j)-x(q[t[i]][i]))>=(y(j)-y(q[t[i]][i]))*(x(q[t[i]][i])-x(q[t[i]-1][i])))--t[i];     q[++t[i]][i]=j;while(H[j]<T[j]&&(Y(Q[H[j]+1][j])-Y(Q[H[j]][j]))<=(X(Q[H[j]+1][j])-X(Q[H[j]][j]))*2*s[i-1]) ++H[j];if(j>1) f[i][j]=max(f[i][j],f[Q[H[j]][j]][j-1]+a[i]*b[j]-(s[i-1]-s[Q[H[j]][j]])*(s[i-1]-s[Q[H[j]][j]]));while(H[j]<T[j]&&(Y(Q[T[j]][j])-Y(Q[T[j]-1][j]))*(X(i)-X(Q[T[j]][j]))>=(Y(i)-Y(Q[T[j]][j]))*(X(Q[T[j]][j])-X(Q[T[j]-1][j])))--T[j];     Q[++T[j]][j]=i;ans=max(ans,f[i][j]-(s[n]-s[i])*(s[n]-s[i])-(S[n]-S[j])*(S[n]-S[j]));}}return !printf("%lld",ans);
}