CF889E 不知道是不是新做法
Purslane
·
·
个人记录
Solution
显然我们只保留 a 的前缀 min，然后把每个位置挂在他前面第一个前缀 min 是。大概这样：
然后记第 i 个前缀 min 的值是 b_i。记前缀 min 的个数是 m。记前 k 个前缀 min 包含了 pre_k 个元素。
我们设计这样一个 DP：dp_i 表示，将前 i 个 b 全部改成 b_i，能获得的最大答案。
考虑 $dp_i$ 转移。记 $X \bmod b_i = x_1$，$x_1 \bmod b_{i+1} = x_2$。
那么显然 $x_1 = x_2 + k \times b_{i+1}$，$k$ 是一个自然数。
假设我们知道 $x_2$，一定会让 $x_1$ 尽量大。
发现：$x_2 \le b_i \bmod b_{i+1}$ 时，$x_1 = x_2 + \lfloor \frac{b_i}{b_{i+1}} \rfloor b_{i+1}$；否则，$x_1 = x_2 + (\lfloor \frac{b_i}{b_{i+1}} \rfloor-1) b_{i+1}$。
如果我们选的是后者，那么相当于转移到 $dp_{i+1}$，但是多了 $pre_{i} \times (\lfloor \frac{b_i}{b_{i+1}} \rfloor-1) b_{i+1}$，也就是
$$
dp_i \leftarrow dp_{i+1} + pre_{i} \times (\lfloor \frac{b_i}{b_{i+1}} \rfloor-1) b_{i+1}
$$
如果选的是前者，即 $x_2 \le b_i \bmod b_{i+1}$。那我们找到第一个 $b_j$ 使得 $b_j < b_i \bmod b_{i+1}$。容易知道在 $(i,j)$ 中的 $b$ 都是没有用的。再分析下一次取模的结果和 $(b_i \bmod b_{i+1}) \bmod b_j$ 的大小关系。可以直接从 $dp_j$ 转移，也可以再拿到 $(b_i \bmod b_{i+1}) \bmod b_j$ 往后继续转移。
每取模一次会减半，所以我们只会进行 $O(\log V)$ 次操作。故复杂度为 $O(n \log V \log n)$。
```cpp
#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2e5+10;
int n,m,a[MAXN],len[MAXN],mod[MAXN],pos[MAXN],pre[MAXN],dp[MAXN];
int bfind(int l,int r,int v) {
int ans=r+1;
while(l<=r) {
int mid=(l+r>>1);
if(mod[mid]<v) ans=mid,r=mid-1;
else l=mid+1;
}
return ans;
}
signed main() {
// freopen("ternarysearch.in","r",stdin);
// freopen("ternarysearch.out","w",stdout);
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
ffor(i,1,n) cin>>a[i];
int lst=LONG_LONG_MAX;
ffor(i,1,n) if(a[i]<lst) ++m,pos[m]=i,mod[m]=a[i],lst=a[i];
lst=n+1;
roff(i,m,1) len[i]=lst-pos[i],lst=pos[i];
ffor(i,1,m) pre[i]=pre[i-1]+len[i];
dp[m]=(mod[m]-1)*n;
roff(i,m-1,1) {
dp[i]=pre[i]*((mod[i]/mod[i+1])-1)*mod[i+1]+dp[i+1];
int ex=pre[i]*(mod[i]/mod[i+1]*mod[i+1]),MOD=mod[i]%mod[i+1];
while(1) {
int pos=bfind(1,m,MOD);
if(pos==m+1) {dp[i]=max(dp[i],ex+(MOD-1)*n);break ;}
dp[i]=max(dp[i],ex+((MOD/mod[pos]-1)*mod[pos])*pre[pos-1]+dp[pos]);
ex+=MOD/mod[pos]*mod[pos]*pre[pos-1];
MOD%=mod[pos];
}
}
cout<<dp[1];
return 0;
}
```