【树形DP】【斜率优化】Tommy的结合
分析:
技巧比较多的一道题。
题目本身思维难度不算太大,主要是套路很多。
首先,有一个很显然的DP
定义表示i和j匹配的情况下的最大贡献。转移时需要枚举下一个匹配点分别在哪,所以总的复杂度为。然后就是非常套路地DP优化。
对于这种匹配类问题,可以换一种DP定义方式:
表示i与j匹配时的最大贡献(即上面的DP)
表示,A选择的与下一个B选择的数相匹配的最大贡献(即此时A多选一个数)
这样定义DP后,可以发现,每次只需要枚举下一个点即可:
所以现在整个复杂度压到了
然后,观察这个式子,发现可以斜率优化。
然后就是套路地树上斜率优化即可。
简述一下树上斜率优化的过程:
与普通的序列斜率优化不同,不能依次弹出队尾/队首元素,需要二分到合适的斜率位置弹出。同时,由于是树上斜率优化,所以要考虑访问某个子树后,再回来的情况,此时必须排除所有之前子树的节点的影响。这时如果依次弹回来显然是比较劣的。正确的姿势是:
由于每次插入一个元素,有两种情况:
1、删除队尾的一段,再把删完后的队尾+1位置修改成当前点。
2、删除队首的一段。
所以,可以记录加入当前这个点的影响前,其左端点/右端点原始的位置。以及当前点原来的数值。就可以做到O(1)消去一个点在我们维护的凸壳中的影响。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define SF scanf
#define PF printf
#define x first
#define y second
#define MAXN 2700
#define INF (1ll<<60)
using namespace std;
typedef long long ll;
void Read(int &x){
x=0;
char c;
bool flag=0;
while(c=getchar(),c!=EOF&&(c<'0'||c>'9')&&c!='-');
if(c=='-') flag=1;
else x=c-'0';
while(c=getchar(),c!=EOF&&c>='0'&&c<='9') x=x*10+c-'0';
if(flag) x=-x;
}
int pa[MAXN],pb[MAXN],ta[MAXN],tb[MAXN];
int val[MAXN][MAXN];
int old1[MAXN][MAXN],now;
ll ans=-INF;
double get_k(pair<int,ll> a,pair<int,ll> b){
return double(b.y-a.y)/(b.x-a.x);
}
vector<int> a[MAXN],b[MAXN];
struct Bac{
bool flag;
int pos;
double k;
pair<int,ll> p;
};
struct node{
pair<int,ll> q[MAXN];
double k[MAXN];
Bac bac[MAXN*2];
int top,l,r;
void clear(){
top=r=0;
l=1;
k[1]=1.0/0.0;
}
void add(pair<int,ll> x){
bac[++top].flag=1;
bac[top].pos=r;
if(l>r||k[r]>get_k(q[r],x))
r++;
else{
int l1=l,r1=r,res=l;
while(l1<=r1){
int mid=(l1+r1)>>1;
if(k[mid]>get_k(q[mid],x))
l1=mid+1;
else{
res=mid;
r1=mid-1;
}
}
r=res;
}
bac[top].p=q[r];
bac[top].k=k[r];
q[r]=x;
if(l<r)
k[r]=get_k(q[r-1],x);
else
k[r]=1.0/0.0;
}
ll query(ll k1){
bac[++top].flag=0;
bac[top].pos=l;
int l1=l,r1=r,res=l;
while(l1<=r1){
int mid=(l1+r1)>>1;
if(k[mid]>=k1){
res=mid;
l1=mid+1;
}
else
r1=mid-1;
}
l=res;
return q[l].y-k1*q[l].x;
}
void dework(int old){
while(top>old){
if(bac[top].flag==1){
q[r]=bac[top].p;
k[r]=bac[top].k;
r=bac[top].pos;
}
else
l=bac[top].pos;
top--;
}
}
}Qf[MAXN],Qg;
ll f[MAXN][MAXN],g[MAXN][MAXN];
ll sqr(ll x){
return x*x;
}
void dfsB(int x,int fa=1){
int old=Qg.top;
int tax=ta[now],tax1=ta[pa[now]];
int tbx=tb[x],tbx1=tb[pb[x]];
f[now][x]=Qf[x].query(-2*tax1)-sqr(tax1)+val[now][x];
ans=max(ans,f[now][x]);
if(pb[x]!=1)
g[now][x]=Qg.query(-2*tbx1)-sqr(tbx1);
Qg.add(make_pair(tbx,f[now][x]-sqr(tbx)));
if(pb[x]!=1)
Qf[x].add(make_pair(tax,g[now][x]-sqr(tax)));
for(int i=0;i<int(b[x].size());i++)
dfsB(b[x][i],x);
Qg.dework(old);
}
int n,m;
void dfsA(int x,int fa=1){
int *old=old1[x];
Qg.clear();
now=x;
for(int i=2;i<=m;i++)
old[i]=Qf[i].top;
for(int i=0;i<int(b[1].size());i++)
dfsB(b[1][i]);
for(int i=0;i<int(a[x].size());i++)
dfsA(a[x][i],x);
for(int i=2;i<=m;i++)
Qf[i].dework(old[i]);
}
int main(){
Read(n),Read(m);
for(int i=2;i<=n;i++) Read(ta[i]);
for(int i=2;i<=m;i++) Read(tb[i]);
for(int i=2;i<=n;i++){
Read(pa[i]);
a[pa[i]].push_back(i);
}
for(int i=2;i<=m;i++){
Read(pb[i]);
b[pb[i]].push_back(i);
}
for(int i=2;i<=n;i++) ta[i]+=ta[pa[i]];
for(int i=2;i<=m;i++) tb[i]+=tb[pb[i]];
for(int i=2;i<=n;i++)
for(int j=2;j<=m;j++)
Read(val[i][j]);
for(int i=1;i<=m;i++){
Qf[i].clear();
Qf[i].add(make_pair(0,-sqr(tb[pb[i]])));
}
for(int i=0;i<int(a[1].size());i++)
dfsA(a[1][i]);
PF("%lld\n",ans);
}