惠州网站设计培训,东莞动点网络科技有限公司,湖北企业网站优化排名,网站开发技术的雏形 cgi正题
CF889E luogu 题目大意
给你 n 个数#xff0c;让你选择一个X#xff0c;使得 ∑i1nXmoda1moda2...modai\sum_{i1}^nX\mod a_1\mod a_2...\mod a_i∑i1nXmoda1moda2...modai 最大 解题思路
可以发现必定存在一个 i #xff0c;使得当前点贡献为 aia_iai让你选择一个X使得 ∑i1nXmoda1moda2...modai\sum_{i1}^nX\mod a_1\mod a_2...\mod a_i∑i1nXmoda1moda2...modai 最大 解题思路
可以发现必定存在一个 i 使得当前点贡献为 aia_iai否则把 X 加一显然可以得到更优的答案
朴素的状态转移很难优化考虑令 fi,jf_{i,j}fi,j 表示到第 i 个点当前值为 0∼j0\sim j0∼j当前总贡献为 i×(0∼j)fi,ji\times (0\sim j)f_{i,j}i×(0∼j)fi,j即把 j 个状态存到了一起然后把模后的贡献存在 f 中
对于 ai1ja_{i1}jai1j直接传递即可
否则存在两种转移
fi1,jmodai1max(fi,ji×(j−jmodai1)fi1,ai1−1max(fi,ji×(((j1)/ai1×ai1−1)−(ai1−1))f_{i1,j\mod a_{i1}}max(f_{i,j}i\times (j-j\mod a_{i1}) \\ f_{i1,a_{i1}-1}max(f_{i,j}i\times(((j1)/a_{i1}\times a_{i1}-1)-(a_{i1}-1)) fi1,jmodai1max(fi,ji×(j−jmodai1)fi1,ai1−1max(fi,ji×(((j1)/ai1×ai1−1)−(ai1−1))
第二个转移即找到最大的值使其转移到 ai1−1a_{i1}-1ai1−1
因为一个数模了之后至少减半所以最多转移 logxlog\ xlog x次
时间复杂度 O(nlognlogx)O(nlog\ n\ log\ x)O(nlog n log x) code
#includemap
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
using namespace std;
mapll,ll::iterator it;
ll n,x,y,z,ans;
mapll,llf;
int main()
{scanf(%lld,n);for(int i1;in;i){scanf(%lld,x);if(i1)f[x-1]0;else{for(itf.lower_bound(x);it!f.end();f.erase(it)){y(*it).first;z(*it).second;f[y%x]max(f[y%x],z(i-1)*(y-y%x));f[x-1]max(f[x-1],z(i-1)*((y1)/x*x-x));}}}for(itf.begin();it!f.end();it)ansmax(ans,(*it).first*n(*it).second);printf(%lld,ans);return 0;
}
