题解：CF2171H Shiori Miyagi and Maximum Array Score

· · 题解

思路

朴素 dp 做法，f_{i,j} 表示当 a_i=j 时，目前最大值。转移方程 f_{i,j}=\max_{k=1}^{j-1} f_{i-1,k}+v(i,j)，时间复杂度 O(n^2)。

假做法

由于 v(i,j) 当且仅当在 i \mid j 时不为 0，故有效状态只有 O(n \ln n)。

挑出这 O(n \ln n) 个决策点，并按照 i 排序，用树状数组计算 \max_{k=1}^{j-1} f_{i-1,k} 最大值加上 v(i,j) 就是当前答案。

答案就是从所有 n-i \le m-j 的决策点中，挑出最大值即可（这样保证能剩下的够选 n 个数）。

修正假做法

发现答案算大，hack 如下。 :::info[Hack]{open}

1
4 10

::: 正确答案 5，而你输出 6。

这是因为 f_{a,b} 能到 f_{c,d}。不仅要满足 a<c，还要满足 b-a \leq d-c（这个可以理解为由于可以选或不选，j-i 的值不降）。

所以将决策点按 j-i 大小为第一关键字，i 为第二关键字排序即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn=200005,maxs=2272115;
int T,n,m,ans,siz,now;
struct pos{
    int x,y;
    bool operator < (const pos b) const {return y-x<b.y-b.x||y-x==b.y-b.x&&x<b.x;}
}p[maxs];
namespace dhcio{
    inline int read(){
        char ch=getchar();int ret=0,f=1;
        while(ch<'0'||ch>'9'){if(ch=='-') f=-f;ch=getchar();}
        while(ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+(ch&15),ch=getchar();
        return ret*f;
    }
    inline void write(int x){
        if(x<0) x=-x,putchar('-');
        if(x>9) write(x/10);
        putchar('0'+x%10);
    }
}
using namespace dhcio;
struct BIT{
    int tree[maxn];
    void init(){for(int i=1;i<=n;i++) tree[i]=0;}
    void add(int x,int v){for(;x<=n;x+=x&-x) tree[x]=max(tree[x],v);}
    int get(int x){int sum=0;for(;x;x-=x&-x) sum=max(sum,tree[x]);return sum;}
}S;
int calc(int x,int y){int sum=0;while(y%x==0) sum++,y/=x;return sum++;}
void solve(){
    n=read(),m=read();siz=ans=0;S.init();
    for(int i=2;i<=n;i++)
    for(int j=i;j<=m;j+=i)
      if(m-j>=n-i) p[++siz]=(pos){i,j};
    sort(p+1,p+1+siz);
    for(int i=1;i<=siz;i++){
        now=S.get(p[i].x-1)+calc(p[i].x,p[i].y);
        S.add(p[i].x,now);ans=max(ans,now);
    }
    write(ans);putchar('\n');
}
signed main(){
    T=read();
    while(T--) solve();
    return 0;
}