CF_#445(Div. 1)_E

题目传送门
比赛打到一半CF炸了,感觉非常的累……

题意:给你序列$a_{i}$,定义$f(x,n)=x \% a_{n},f(x,i)=x \% a_{i} + f(x \% a_{i},i + 1)$,求函数$f(x,1)$的最大值.
分析:$f(x,1)=x \% a_{1} + x \% a_{1} \% a_{2} + \dots + x \% a_{1} \% a_{2} \dots \% a_{n}$,定义$b_{x,i} = x \% a_{1} \% a_{2} \dots \% a_{i}$.
定理: 如果$f(m,1)$是最大值,那么一定存在至少一个$i$使得$b_{m,i} = a_{i} - 1$.
证明:反证法,如果$f(m,1)$是最大值且不满足上述条件,那么对于$f(m + 1,1)$,我们可以得到$b_{m+1,i} = b_{m,i} + 1$,那么$f(m,1)$就肯定不是最大值,得证.
做法: 用$map$维护一个$pair(c,w)$表示当$0 \leq b_{x,i} \leq c$时,前$i$个数的比$c$多的部分的和的最大值.当$a_{i} > c$时$w$不变;当$a_{i} \leq c$时区间由$[0,c]$变成$[0,a_{i}-1],[0,c \% a_{i}]$.答案就是$max(w + c * n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//created by missever
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> P;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
map<LL,LL> q;
vector<P> f;
int main(){
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int n,i;
LL x,p;
scanf("%d",&n);
scanf("%lld",&p);
q[p - 1] = 0;
for(i = 1;i < n; i++) {
scanf("%lld",&x);
if(x >= p) continue;
f.clear();
auto e = q.lower_bound(x);
for(auto u = e;u != q.end(); u++) f.push_back(*u);
q.erase(e,q.end());
for(auto u:f) {
q[x - 1] = max(q[x - 1],(u.first - x + 1) / x * x * i + u.second);
q[u.first % x] = max(q[u.first % x],u.first / x * x * i + u.second);
}
}
x = 0;
for(auto e:q) x = max(x,e.first * n + e.second);
printf("%lld\n",x);
return 0;
}