题解：CF2048F Kevin and Math Class

· · 题解

题目传送门

题目大意

给出两个序列 A 和 B，每次操作可以选择一个区间 [l,r]，记 x 为序列 B 在这个区间内的最小值，把 A 区间对应的位置上的数都除以 x 向上取整，求把 A 序列中所有数都变成 1 所需的最小操作次数。

解题思路

我们注意到一个性质，对于 B 中的一个数 b_i，当以它为区间最小值时，操作的区间一定是满足它是最小值的最大区间 [l,r] 这样一定最优。

那么该怎么预处理出每个 b_i 所对应的区间呢，我们想到可以用小根笛卡尔树来维护，这样每一个节点就是自己子树所在区间的最小值。这样我们就可以在笛卡尔树上从叶子往根进行树形 dp。

现在我们考虑该怎么动规，由于 b_i\ge 2，所以对于所有情况最多只会除 63 次就是上限了。我们定义 dp_{i,j} 表示在以 i 为根的子树内进行 j 次操作后 A 中的最大值是多少。我们可以把情况分为三类。

第一类是节点为叶子节点，这种情况最好处理，我们只用处理自己这个节点的 a_i 除以 b_i 即可。

if(!l[u]&&!r[u]){
    dp[u][0]=a[u];
    for(int i=1;i<=63;i++)dp[u][i]=dp[u][i-1]/b[u];
    return ;
}

第二类是只有一个儿子的节点，这种情况我们先处理它和它儿子之间的大小关系，然后再根据处理后的数组进行转移。就相当于先算出它儿子自己要先操作多少次再和它一起操作多少次。

if(!l[u]||!r[u]){
    ll v=l[u]?l[u]:r[u];
    dfs(v);
    for(int i=0;i<=63;i++)dp[u][i]=max(dp[v][i],a[u]);
    for(int i=1;i<=63;i++)dp[u][i]=min(dp[u][i],dp[u][i-1]/b[u]);
    return ;
}

最后一种情况就是这个节点有两个节点，那么就要算出左边的儿子要自己操作多少次，右边的要自己操作多少次再和自己一起操作。这里可以用一个类似背包的思路去计算。

dfs(l[u]),dfs(r[u]);
for(int i=0;i<=63;i++)
    for(int j=0;j<=i;j++)
        dp[u][i]=min(dp[u][i],max(a[u],max(dp[l[u]][j],dp[r[u]][i-j])));
for(int i=1;i<=63;i++)dp[u][i]=min(dp[u][i],dp[u][i-1]/b[u]);

最后记得多测清空。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=201010;
ll n,a[N],b[N],st[N],l[N],r[N],dp[N][64],top;
void dfs(ll u){
    if(!l[u]&&!r[u]){
        dp[u][0]=a[u];
        for(int i=1;i<=63;i++)dp[u][i]=dp[u][i-1]/b[u];
        return ;
    }
    if(!l[u]||!r[u]){
        ll v=l[u]?l[u]:r[u];
        dfs(v);
        for(int i=0;i<=63;i++)dp[u][i]=max(dp[v][i],a[u]);
        for(int i=1;i<=63;i++)dp[u][i]=min(dp[u][i],dp[u][i-1]/b[u]);
        return ;
    }
    dfs(l[u]),dfs(r[u]);
    for(int i=0;i<=63;i++)
        for(int j=0;j<=i;j++)
            dp[u][i]=min(dp[u][i],max(a[u],max(dp[l[u]][j],dp[r[u]][i-j])));
    for(int i=1;i<=63;i++)dp[u][i]=min(dp[u][i],dp[u][i-1]/b[u]);
    return ;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll T;
    cin>>T;
    while(T--){
        top=0;
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i],a[i]--;
        for(int i=1;i<=n;i++)cin>>b[i],l[i]=r[i]=0;
        st[++top]=1;
        for(int i=2;i<=n;i++){
            while(top&&b[i]<b[st[top]])l[i]=st[top],top--;
            if(top)r[st[top]]=i;
            st[++top]=i;
        }
        for(int i=1;i<=n;i++)for(int j=0;j<=63;j++)dp[i][j]=1e18;
        dfs(st[1]);
        for(int i=0;i<=63;i++){
            if(!dp[st[1]][i]){
                cout<<i<<"\n";
                break;
            }
        }
    }

    return 0;
}