CF889E Mod Mod Mod
题意
题解
很有意思的一题啊。
首先我们想一下已经固定了 \(x\) 改怎么快速做。
显然我们在序列中找到第一个比自己小的数进行操作。
取完模之后值域会变为前面的一半，所以最多只会跳 \(logV\) 段。
但这样并没有什么栾用，不好确定 \(x\)，所以考虑 \(dp\)。
设 \(b_i\) 为操作到 \(i\) 时得到的数，\(f_{i,j}\) 表示操作到 \(i,b_i=j\) 时 \(\max\sum_{j=1}^{j\leq i}b_j\)。
这个 \(dp\) 直接按照操作去转移很简单，但是状态数和值域有关，会寄掉。
这样太难搞了，值域太大，而且没有什么特殊性质去做，很难办。
发现一个性质。
若 \(b_i \not=0\)，则若初始值变为 \(x+1\)，并且操作到 \(i\) 时 \(b_i' \not ={0}\)，则 \(b_i'=b_i+1\) 。
根据这个性质我们就可以推出另一个结论，一个比较有的初始值至少会到一个 \(i\) 时使得 \(k=a_i-1\)。
现在计算答案的方式有些复杂，注意到答案可以写成 \(xn-y\) 的形式，选一个 \(x\) 为基准线，\(y\) 就是得到的差值。
修改一下 \(dp\) 的状态，设 \(f_{i,j}\) 表示 操作到 \(i\)，基准线为 \(j\) 的最大的 \(y\) 。
这个的转移容易通过一个简单的增量得到，\(f_{i,j'} = f_{i,j}+(j-j')i\) 。
这个状态结合之前得到的性质之后就有一个优雅的性质。
\(\forall j<i,b_j \not ={0}\)，则 \([0,b_i]\) 对应的 \(y\) 都相等，可以由第一个性质证明。
所以可以再次优化状态 \(f_{i,j}\) 表示 \([0,j]\) 对应的最大的 \(y\)，再考虑枚举 \(k，k < j\)，进行转移。
根据第二个性质可以得到最优决策点，可得转移:
上面是直接转移，后面是找到满足 \(b_i = a_{i+1}-1\) 的最优决策点。
用 map转移即可。
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define rg register
#define pc putchar
#define gc getchar
#define pf printf
#define space pc(' ')
#define enter pc('\n')
#define me(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define FOR(i,k,t,p) for(rg int i(k) ; i <= t ; i += p)
#define ROF(i,k,t,p) for(rg int i(k) ; i >= t ; i -= p)
using namespace std ;
bool s_gnd ;
inline void read(){}
template<typename T,typename ...T_>
inline void read(T &x,T_&...p)
{
x = 0 ;rg int f(0) ; rg char c(gc()) ;
while(!isdigit(c)) f |= (c=='-'),c = gc() ;
while(isdigit(c)) x = (x<<1)+(x<<3)+(c^48),c = gc() ;
x = (f?-x:x) ;
read(p...);
}
int stk[30],tp ;
inline void print(){}
template<typename T,typename ...T_>
inline void print(T x,T_...p)
{
if(x < 0) pc('-'),x = -x ;
do stk[++tp] = x%10,x /= 10 ; while(x) ;
while(tp) pc(stk[tp--]^48) ; space ;
print(p...) ;
}
bool S_GND ;
const int N = 2e5+5 ;
int n,ans ;
int a[N] ;
map<int,int>f ;
signed main()
{
//cerr<<(double)(&s_gnd-&S_GND)/1024.0/1024.0 ;
// freopen(".in","r",stdin) ;
// freopen(".out","w",stdout) ;
read(n) ;
FOR(i,1,n,1) read(a[i]) ;
f[a[1]-1] = 0 ;
FOR(i,1,n-1,1)
{
for(auto it = f.lower_bound(a[i+1]) ; it != f.end() ; f.erase(it++))
{
auto [x,y] = *it ;
f[x%a[i+1]] = max(f[x%a[i+1]],y+(x-x%a[i+1])*i) ;
f[a[i+1]-1] = max(f[a[i+1]-1],y+((x+1)/a[i+1]*a[i+1]-a[i+1])*i) ;
}
}
for(auto [x,y]:f) ans = max(ans,x*n+y) ; print(ans) ;
return 0 ;
}