题目大意: 给出正整数 \(n\) 和序列 \(\{A_i\}\) ,定义 \(f_k(x) = f_{k-1}(x) \bmod a_k , f_0(x)=x\) ,求 \(\max_x{\sum_{i=1}^n f_k(x)}\) 。
\(n \le 2 \cdot 10^5 , A_i \le 10^{13}\).
首先容易发现答案的 \(x\) 一定是某个 \(A_i-1\) 。
这就可以 \(n^2\) 做了。
然后尝试把 \(n^2\) 用 DP 做,设 \(f_{i,j}\) 为做到第 \(i\) 项,\(f_i(x)=j\) 的答案。
发现所有转移都是有意义转移,不好搞。
考虑 \(x <a_i\) 的时候,贡献都是一样的,所以把贡献变为 \(i \cdot f_i(x) + b\) 的形式,此时 \(j < a_i\) 就不需要转移了。
分析取模的过程发现 \(x\) 每次“有效取模”后至多是原本的一半。
因此只会有 \(O(\log A)\) 次转移发生于此。
做完了。复杂度 \(O(n \log A \log n)\) 。
#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,d) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const int N=2e5+10;
int n,m;
ll a[N];
map<ll,ll> f;
void trans(ll &a,ll b){a=(a>b?a:b);}
int main(){
scanf("%d",&n);
fo(i,1,n)scanf("%lld",&a[i]);
f[a[1]-1]=0;
fo(i,2,n){
for(map<ll,ll>::iterator it=f.lower_bound(a[i]);it!=f.end();++it){
trans(f[it->first % a[i]] , it->second + (ll)(i-1)*(it->first-it->first%a[i]));
if(it->first>=a[i])trans(f[a[i]-1] , it->second + (ll)(i-1)*(it->first - it->first % a[i] -1 - (a[i]-1)));
}
f.erase(f.lower_bound(a[i]),f.end());
}
ll ans=0;
for(auto it:f){
trans(ans , it.second + it.first*n);
}
printf("%lld\n",ans);
return 0;
}
标签:CF889E,int,ll,second,ans,trans,first
From: https://www.cnblogs.com/Kelvin2005/p/16903871.html