BZOJ-1713: [Usaco2007 China]The Bovine Accordion and Banjo Orchestra 音乐会

Description

二维斜率优化DP【实际上就是关于两个维度分别有一个转移方式，两个维度需要分别斜率优化】
发现如果当前i,j配对，那么上一个配对的至少含有i-1或j-1中的一个，证明：如果不含有，将i-1，j-1配对对结果更优。
设dp[i][j]表示手风琴手匹配到i，班卓琴手匹配到j，i,j匹配的最大收益，sa[i]为手风琴手的天才指数的前缀和，sb[i]表示班卓琴手的前缀和。
转移方程：dp[i][j]=
1.max(dp[i-1][k] (0<=k<=j-1)-sb[j]^2+2*sb[j]*sb[k]-sb[k]^2）
2.max(dp[k][j-1] (0<=k<=i-1)-sa[i]^2+2*sa[i]*sa[k]-sa[k]^2)
两种转移分别进行斜率优化，对于每一行维护一个队列，每一列也维护一个队列，对于当前的i,j，将i-1,j加入到关于行和关于列的两个队列中即可。
注意dp[i][j]表示的是i,j匹配的最大收益，所以对于dp[0][1]转移到dp[1][3]是不合法的【第二维1,2需要连着计算平方的代价】

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1100 
typedef long long ll;
int n;
int qa[N][N],al[N],ar[N];
int qb[N][N],bl[N],br[N];
ll a[N],b[N],sa[N],sb[N],dp[N][N],ans=0xefefefefefefefefll;
inline ll calc1(int i,int j,ll x) {return dp[i][j]+sb[j]*2*x-sb[j]*sb[j];}
inline ll calc2(int i,int j,ll x) {return dp[i][j]+sa[i]*2*x-sa[i]*sa[i];}
inline ll Ba(int i,int j){return dp[i][j]-sb[j]*sb[j];}
inline ll Ka(int j){return sb[j]<<1;}
inline ll Bb(int i,int j){return dp[i][j]-sa[i]*sa[i];}
inline ll Kb(int i){return sa[i]<<1;}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%lld",a+i),sa[i]=sa[i-1]+a[i],dp[i][0]=-sa[i]*sa[i];
    for(int i=1;i<=n;++i) scanf("%lld",b+i),sb[i]=sb[i-1]+b[i],dp[0][i]=-sb[i]*sb[i];
    for(int i=0;i<=n;++i) al[i]=bl[i]=1;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            dp[i][j]=a[i]*b[j]-sa[i-1]*sa[i-1]-sb[j-1]*sb[j-1];
            while( al[i-1]<ar[i-1] && (calc1(i-1,qa[i-1][al[i-1]],sb[j-1])<=calc1(i-1,qa[i-1][al[i-1]+1],sb[j-1]) ) ) al[i-1]++;
            if(i>1) dp[i][j]=max(dp[i][j],calc1(i-1,qa[i-1][al[i-1]],sb[j-1])-sb[j-1]*sb[j-1]+a[i]*b[j]);
            while( bl[j-1]<br[j-1] && (calc2(qb[j-1][bl[j-1]],j-1,sa[i-1])<=calc2(qb[j-1][bl[j-1]+1],j-1,sa[i-1]) ) ) bl[j-1]++;
            if(j>1) dp[i][j]=max(dp[i][j],calc2(qb[j-1][bl[j-1]],j-1,sa[i-1])-sa[i-1]*sa[i-1]+a[i]*b[j]);
            while( al[i-1]<ar[i-1] && (Ba(i-1,qa[i-1][ar[i-1]])-Ba(i-1,j))*(Ka(qa[i-1][ar[i-1]])-Ka(qa[i-1][ar[i-1]-1]))
                <= (Ba(i-1,qa[i-1][ar[i-1]-1])-Ba(i-1,qa[i-1][ar[i-1]]))*(Ka(j)-Ka(qa[i-1][ar[i-1]])) ) ar[i-1]--;
            qa[i-1][++ar[i-1]]=j;
            while( bl[j]<br[j] && (Bb(qb[j][br[j]],j)-Bb(i-1,j))*(Kb(qb[j][br[j]])-Kb(qb[j][br[j]-1]))
                <= (Bb(qb[j][br[j]-1],j)-Bb(qb[j][br[j]],j))*(Kb(i-1)-Kb(qb[j][br[j]])) ) br[j]--;
            qb[j][++br[j]]=i-1;
            ans=max(ans,dp[i][j]-(sa[n]-sa[i])*(sa[n]-sa[i])-(sb[n]-sb[j])*(sb[n]-sb[j]));
        }
    }
    printf("%lld",ans);
    return 0;
}