「题解」Codeforces 1612F Armor and Weapons

do_while_true · 2022-11-05 11:07:15 · 题解

首先可以不管套件，假定 n<m，那么答案不超过 \mathcal{O}(\log n+\frac{m}{n})，也就是先倍增把 n 造出来，然后一步步造 m．

答案这么小，那么常见的套路就是把答案放进复杂度里。

然后考虑一个 dp，假设当且在第 o 轮，令 f_i 为手中最牛逼的盔甲是 i，能够拿到最牛逼的武器是 f_i，想要 dp 出第 (o+1) 轮的 f'．

不用套件的转移，购买盔甲是 f'_j\gets f_i,i\leq j\leq i+f_i，购买武器是 f'_i\gets f_i+i．

用套件的话，那么一定是用 i 和 f_i，要不然不会更优，所以也能类似转移。

通过打 tag 然后从后往前取 max 可以做到单次 \mathcal{O}(n) 转移，那么时间复杂度就是 \mathcal{O}(n\log n+m)．

const int N=200010;

int n,m,q,x,y,ans,f[N],g[N],fl;
map<int,int>vis[N];

void solve(){
    read(n,m,q);
    if(n>m)swap(n,m),fl=1;
    while(q--)read(x,y),fl?swap(x,y),0:0,vis[x][y]=1;
    f[1]=1;
    for(;f[n]<m;++ans){
        for(int i=1;i<=n;i++)if(f[i]){
            int k=vis[i][f[i]];
            cmax(g[min(n,i+f[i]+k)],f[i]);
            cmax(g[i],min(m,i+f[i]+k));
        }
        for(int i=n;i>=1;i--)f[i]=max(g[i],f[i+1]),g[i]=0;
    }
    cout << ans << '\n';
}