[JZOJ 5402] God Knows

终于搞完了这乡里别题目
$
$
考虑一个 $dp$ ，设 $f[i]$ 表示最后一个匹配选 $(i,p[i])$ 的最小费用
首先我们考虑答案长什么样
假设根据 $p[i]$ 排序 ,那么答案肯定是一些以 $p[]$ 为下标的区间的费用的总和
如果 $j$ 能够转移到 $i$ ，那么 $j$ 一定处于一个基于原数组下标递减的单调序列中，这个我们可以用一个单调栈维护
这个单调栈要使得栈中的最小值尽量小并且费用尽量小
所以我们就是要对于每一个 $i$ 求出一个 $j$ 使得：

$p[j]<p[i]$；
$j$ 处于 $i$ 左侧的一个单调栈中；
$f[j]$ 最小；
$
$

那么这个东西要怎么处理？
这里上一波套路，线段树维护单调栈（相似题：[BZOJ2957] 楼房重建）
以 $p[]$ 为线段树下标，在线段树的每个区间维护一个单调栈，并在节点记录了两个东西：$mj$，$val$（初值为 $inf$）

$val$ 为该区间的最小费用；
$mj$ 为该区间的最大原数组下标；

对于一个 $i$ ，$f[i]$ 的初值为 $c[i]$，如果 $p[i]$ 大于当前记录的最小 $p[]$ 的值，那么就用区间 $[1,p[i]]$ 的 $val$ 来更新 $f[i]$
然后将新的 $(i,f[i])$ 插入 $p[i]$ 节点来更新线段树以及单调栈
举个栗子（样例）：
$Minp=inf$；
$i=1,p[i]=3,f[i]=3,Minp=3$
线段树叶子节点中存的原数组下标：$\{inf,inf,1,inf,inf\}$

$i=2,p[i]=1,f[i]=4,Minp=1$
线段树叶子节点中存的原数组下标：$\{2,inf,1,inf,inf\}$
节点 $[1,2]$ 的单调栈更新为 $\{2,1\}$，$val=4$
节点 $[1,3]$ 的单调栈更新为 $\{2,1\}$，$val=3$（显然选 $f[1]$ 会更优）

$i=3,p[i]=4,f[i]=3,Minp=1$
这时 $p[i]>Minp$ 了，并且在 $[1,3]$ 中有单调递减的 $\{2,1\}$ 可以为 $f[i]$ 提供贡献，$f[i]=3+3=6$
插入 $f[i]$ 后，节点 $[4,5]$ 中的单调栈更新为$\{3\}$，$val=6$，也就是说，$p[i]>4$的$f[i]$都由$f[3]$来转移
$
$
操作是这样，那么具体到底怎么实现呢？

首先是$query$，对于一个区间，右子树的答案一定是可行的（因为节点的答案插入前已经用左边的答案更新过），
但是右子树的答案不一定是最优的（如果我们能在左子树内找到一个匹配$(i,p[i])$，使得 i 大于右子树内的 $mj$，那么选择这个匹配可能会比右子树的答案更优），所以我们调用这样一个函数 $calc(x<<1,Max)$,$Max$为右子树的 $mj$，即在左子树内寻找一个更优的解，下面会讲
然后是更新（插入）。除了记 $val$，$mj$，我们还要记一个东西：$lv$，表示之前提到的左子树能够提供的所谓更优的解（当然它有可能不是最优解）。显然，$lv$ 就等于左子树的 $calc$ 值
$calc$。假设我们 $calc$ 到一个节点 $x$，如果它右子树的 $mj$ 小于了 $Max$，那么它的右子树对答案肯定是没有贡献的，我么只需要递归左子树；相反，如果它右子树的 $mj$ 大于 $Max$，那么它能够提供的贡献就是 $lv$ 和右儿子$calc$值的 $min$
然后是统计答案，从后往前统计答案，$mx$初值设为$0$，每次找到一个 $p[i]>mx$ 就拿$ans$和$f[i]$取$min$
$
$

下面是代码（这东西讲起来真的有点玄学，但代码还是好理解的），这道题确实有点$SAO$，如果还不理解可以先去做一下[BZOJ2957] 楼房重建，做完应该就理解操作了：

//made by Hero_of_Someone
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define inf (1<<30)
#define N (200010)
#define il inline
#define RG register
using namespace std;
il int gi(){ RG int x=0,q=1; RG char ch=getchar(); while( ( ch<'0' || ch>'9' ) && ch!='-' ) ch=getchar();
  if( ch=='-' ) q=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x; }
il void File(){freopen("knows.in","r",stdin); freopen("knows.out","w",stdout);}

int n,ans,p[N],c[N],f[N];
struct node{int lv,val,mj;}t[N<<2];

il void init(){
   n=gi();
   for(int i=1;i<=n;i++) p[i]=gi();
   for(int i=1;i<=n;i++) c[i]=gi();
   for(int i=1;i<=n<<2;i++) t[i].val=t[i].lv=inf;
}

il int calc(int x,int l,int r,int Max){
   if(l==r) return t[x].mj>Max?t[x].val:inf;
   int mid=(l+r)>>1;
   if(t[x<<1|1].mj<=Max) return calc(x<<1,l,mid,Max);
   else return min(t[x].lv,calc(x<<1|1,mid+1,r,Max));
}

il pair<int,int> query(int x,int l,int r,int k){
   if(l==r) return make_pair(inf,0);
   int mid=(l+r)>>1;
   if(k<=mid) return query(x<<1,l,mid,k);
   else{
      pair<int,int>v=query(x<<1|1,mid+1,r,k);
      return make_pair(min(v.first,calc(x<<1,l,mid,v.second)),max(t[x<<1].mj,v.second));
   }
}

il void update(int x,int l,int r,int k,int newj,int val){
   if(l==r){ t[x].mj=newj,t[x].val=val; return ; }
   int mid=(l+r)>>1;
   if(k<=mid) update(x<<1,l,mid,k,newj,val);
   else update(x<<1|1,mid+1,r,k,newj,val);
   t[x].lv=calc(x<<1,l,mid,t[x<<1|1].mj);
   t[x].mj=max(t[x<<1].mj,t[x<<1|1].mj);
   t[x].val=min(t[x<<1].val,t[x<<1|1].val);
}

il void work(){
   int P=inf;
   for(int i=1;i<=n;i++){
      f[i]=c[i]; P=min(P,p[i]);
      if(p[i]>P) f[i]+=query(1,1,n,p[i]).first;
      update(1,1,n,p[i],i,f[i]);
   }
   P=0,ans=inf;
   for(int i=n;i;i--) if(p[i]>P) P=p[i],ans=min(ans,f[i]);
   printf("%d\n",ans);
}

int main(){ File(); init(); work(); return 0; }

巴特西

[JZOJ 5402] God Knows

最新文章

热门文章