LINK：修改
题面就不放了 大致说一下做法。不愧是dls出的题 以前没见过这种类型的 不过还是自己dp的时候写丑了。
从这道题中得到一个结论 dp方程要写的优美一点 不过写的过丑 优化都优化不了。
容易想到 f[i][j]表示前i个数最大值为aj的最大收益。
那么有(j<=a_i,f[i][j]=f[i-1][k]-a_i+j+b_i.j>a_i,f[i][j]=f[i-1][j])
值得注意的是这个转移不完全 在第二个转移的式子中 决策不全面 强行利用f[i][j] 的单调性进行覆盖 那么第一个决策中k就可以变成j 且第二个转移也是正确的。
const ll MAXN=5010,N=40;
ll n,ans;
ll a[MAXN],b[MAXN];
ll f[MAXN][MAXN];
struct wy{int id,x,y;}t[MAXN];
inline int cmp(wy a,wy b){return a.x<b.x;}
signed main()
{
//freopen("1.in","r",stdin);
get(n);
rep(1,n,i)get(a[i]),t[i].x=a[i],t[i].id=i;
rep(1,n,i)get(b[i]),t[i].y=b[i];
sort(t+1,t+1+n,cmp);
rep(1,n,i)
{
rep(1,n,j)
{
f[i][j]=-INF;
if(a[j]<=a[i])f[i][j]=max(f[i][j],f[i-1][j]-a[i]+a[j]+b[i]);
else f[i][j]=max(f[i][j],f[i-1][j]);
}
rep(2,n,j)f[i][t[j].id]=max(f[i][t[j-1].id],f[i][t[j].id]);
}
rep(1,n,i)ans=max(ans,f[n][i]);
putl(ans);return 0;
}
值得注意的是 需要赋初值.
这个dp 可以发现 非常不可优化 所以我就弃疗了。
原因是 状态转移方程写丑了 少考虑了情况 导致f值不再单调 需要后来的 单调覆盖。
观察第一个式子 容易想到 如果出现覆盖的情况 那么说明大的j没有前面(b_i)的贡献才会这样。
考虑后面的式子 其实是可以加入这个决策转移的 (f[i][j]=max(f[i-1][j],f[i-1][i]+b_i))
这样f数组显然 单调 那么久不需要单调覆盖了。
具体观察两个dp式子:(j>a_i,f[i][j]=max(f[i-1][j],f[i-1][i]+b_i),j<=a_i,f[i][j]=f[i-1][k]-a_i+j+b_i)
第二个转移 显然是一个加上常数 加上一个端点值j的操作 第一个操作由于f值单调 所以这是一个区间赋值操作。
可以发现没有区间最值 所以线段树可以维护这个转移。至于区间赋值操作 显然可以在查到值之后进行线段树上二分寻找区间即可。
注意 每次修改后注意pushup某个区间的左端点的值 为线段树上二分做准备。
const int MAXN=500010,N=40;
int n,num,cnt;ll ww;
int a[MAXN],b[MAXN],c[MAXN];
struct wy
{
int l,r;
ll sum;
ll tag,tag1,tag2;
}t[MAXN<<2];
inline void discrete()
{
sort(c+1,c+1+n);
rep(1,n,i)if(i==1||c[i]!=c[i-1])c[++cnt]=c[i];
rep(1,n,i)a[i]=lower_bound(c+1,c+1+cnt,a[i])-c;
}
inline void build(int p,int l,int r)
{
l(p)=l;r(p)=r;sum(p)=0;
tag2(p)=-INF;
if(l==r)return;
int mid=(l+r)>>1;
build(zz,l,mid);
build(yy,mid+1,r);
}
inline void pushdown(int p)
{
if(tag2(p)!=-INF)
{
sum(zz)=tag2(p);
sum(yy)=tag2(p);
tag2(zz)=tag2(p);
tag2(yy)=tag2(p);
tag1(zz)=tag1(yy)=0;
tag(zz)=tag(yy)=0;
tag2(p)=-INF;
//return;
}
sum(zz)+=tag(p);
sum(yy)+=tag(p);
tag(zz)+=tag(p);
tag(yy)+=tag(p);
int mid=(l(p)+r(p))>>1;
sum(zz)+=tag1(p)*c[l(p)];
sum(yy)+=tag1(p)*c[mid+1];
tag1(zz)+=tag1(p);
tag1(yy)+=tag1(p);
tag(p)=tag1(p)=0;
}
inline void change(int p,int l,int r,ll v)
{
if(l<=l(p)&&r>=r(p))
{
sum(p)+=v;tag(p)+=v;
sum(p)+=c[l(p)];
++tag1(p);
return;
}
pushdown(p);
int mid=(l(p)+r(p))>>1;
if(l<=mid)change(zz,l,r,v);
if(r>mid)change(yy,l,r,v);
sum(p)=sum(zz);
}
inline ll ask(int p,int x)
{
if(l(p)==r(p))return sum(p);
int mid=(l(p)+r(p))>>1;
pushdown(p);
if(x<=mid)return ask(zz,x);
return ask(yy,x);
}
inline int ask1(int p,int l)
{
if(l(p)>=l&&sum(p)>ww)return 0;
if(l(p)==r(p))return l(p);
int mid=(l(p)+r(p))>>1;
pushdown(p);
if(l>mid)return ask1(yy,l);
int w=ask1(yy,l);
if(!w)return ask1(zz,l);
return w;
}
inline void modify(int p,int l,int r,ll v)
{
if(l<=l(p)&&r>=r(p))
{
sum(p)=v;
tag1(p)=tag(p)=0;
tag2(p)=v;
return;
}
pushdown(p);
int mid=(l(p)+r(p))>>1;
if(l<=mid)modify(zz,l,r,v);
if(r>mid)modify(yy,l,r,v);
sum(p)=sum(zz);
}
signed main()
{
//freopen("1.in","r",stdin);
get(n);
rep(1,n,i)get(a[i]),c[i]=a[i];
rep(1,n,i)get(b[i]);
discrete();
build(1,1,cnt);
rep(1,n,i)
{
change(1,1,a[i],-c[a[i]]+b[i]);
ww=ask(1,a[i]);
int r=ask1(1,a[i]);
//cout<<r<<endl;
modify(1,a[i],r,ww);
}
ll ans=0;
rep(1,cnt,i)ans=max(ans,ask(1,i));
putl(ans);return 0;
}