首先\(i\)越大\(j\)越大
所以dp，\(f_{i,j}\)表示\(a_i\)和\(b_j\)配的最大獲利
所以有\(f_{i,j}=max\{f_{t,k}-(sb_{j-1}-sb_{k})^2-(sa_{i-1}-sa_{t})^2\}\)，其中\(sa，sb\)兩數組的前綴和
又可以發現最優的轉移滿足\(t=i-1，k=j-1\)這兩個其中之一，因為如果不滿足，可以選\(a_{i-1}\)和\(b_{j-1}\)配對，答案更優
所以dp方程式可以表示為\(f_{i,j}=max\{f_{i-1,t}-(sb_{j-1}-sb_t)^2,f_{k,j-1}-(sa_{i-1}-sa_k)^2\}\)
現在兩種轉移分開考慮，化簡，得到\(t\)比\(k\)優的情況，滿足
\[ \frac{g_t-g_k}{sb_t-sb_k}>-2sb_{j-1}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,① \]\[ \frac{g_t-g_k}{sa_t-sa_k}>-2sa_{i-1}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,② \]
其中①中的\(g_t=f_{i-1,t}-sb_t^2\)，②中的\(g_t=f_{t,j-1}-sa_t^2\)
維護兩個上凸殼，搞一個二維的斜率優化就可以了
代碼略(特別)丑
代碼如下：
#include<algorithm>
#include<ctype.h>
#include<cstdio>
#define INF 21474836470000ll
#define N 1050
using namespace std;
inline int read(){int x=0,f=1;char c;do c=getchar(),f=c=='-'?-1:f; while(!isdigit(c));do x=(x<<3)+(x<<1)+c-'0',c=getchar(); while(isdigit(c));return x*f;
}
typedef long long LL;
int n,l,r;
int a[N],b[N],ly[N],ry[N];
LL ans;
LL sa[N],sb[N],f[N][N];
struct Point{LL x,y;Point(){}Point(LL _,LL __):x(_),y(__){}
}qi[N],qj[N][N],tmp;
inline double Slope(Point a,Point b){if(a.x==b.x) return a.y>b.y?-INF:INF;return 1.0*(b.y-a.y)/(b.x-a.x);
}
int main(){n=read();for(int i=1;i<=n;i++){a[i]=read();sa[i]=sa[i-1]+a[i];}for(int i=1;i<=n;i++){b[i]=read();sb[i]=sb[i-1]+b[i];}for(int i=1;i<=n;i++)ly[i]=1;for(int i=1;i<=n;i++){l=1;r=0;for(int j=1;j<=n;j++){f[i][j]=a[i]*b[j]-sa[i-1]*sa[i-1]-sb[j-1]*sb[j-1];while(l<r && Slope(qi[l],qi[l+1])>-sb[j-1]*2)l++;if(i>0 && l<=r)f[i][j]=max(f[i][j],qi[l].y+sb[j-1]*2*qi[l].x-sb[j-1]*sb[j-1]+1ll*a[i]*b[j]);/上面是從i-1轉移while(ly[j]<ry[j] && Slope(qj[j][ly[j]],qj[j][ly[j]+1])>-sa[i-1]*2)ly[j]++;if(j>0 && ly[j]<=ry[j])f[i][j]=max(f[i][j],qj[j][ly[j]].y+sa[i-1]*2*qj[j][ly[j]].x-sa[i-1]*sa[i-1]+1ll*a[i]*b[j]);/從j-1轉移if(i-1){tmp=Point(sb[j],f[i-1][j]-sb[j]*sb[j]);while(l<r && Slope(qi[r],tmp)>Slope(qi[r-1],qi[r]))r--;if(i-1) qi[++r]=tmp;}///上下全是更新隊列if(j-1){tmp=Point(sa[i],f[i][j-1]-sa[i]*sa[i]);while(ly[j]<ry[j] && Slope(qj[j][ry[j]],tmp)>Slope(qj[j][ry[j]-1],qj[j][ry[j]]))ry[j]--;qj[j][++ry[j]]=tmp;}}}for(int i=1;i<=n;i++)ans=max(ans,max(f[i][n]-(sa[n]-sa[i])*(sa[n]-sa[i]),f[n][i]-(sb[n]-sb[i])*(sb[n]-sb[i])));printf("%lld",ans);return 0;
}
轉載于:https://www.cnblogs.com/Duan2baka/p/8674374.html
總結
以上是生活随笔為你收集整理的BZOJ[1713][Usaco2007 China]The Bovine Accordion and Banjo Orchestra 音乐会 二维斜率优化的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
