【luogu CF889E】Mod Mod Mod(性质)(DP)
Mod Mod Mod
题目链接:luogu CF889E
题目大意
f
(
x
,
n
)
=
1
f(x,n)=1
f(x,n)=1
f
(
x
,
i
)
=
(
x
m
o
d
a
i
)
+
f
(
x
m
o
d
a
i
,
i
+
1
)
f(x,i)=(x\mod a_i)+f(x\mod a_i,i+1)
f(x,i)=(xmodai)+f(xmodai,i+1)
然后给你数组
a
a
a,要你找到一个 x 使得
f
(
x
,
1
)
f(x,1)
f(x,1) 最大,输出这个
f
(
x
,
1
)
f(x,1)
f(x,1) 即可。
思路
首先有一个很神奇的东西就是一定会有一个数组中的数 a i a_i ai 到它的贡献是 a i − 1 a_i-1 ai−1(否则你可以把这个数变大 1 1 1,所以位置的贡献都 + 1 +1 +1)
然后设 f i , j f_{i,j} fi,j 为前 i i i 个数组搞定了,然后当前是 j j j 的取模漏了的贡献(也就是一个位置贡献是 i ∗ j + f i , j i*j+f_{i,j} i∗j+fi,j)
然后有一个东西是 f i , j = max { f i , k } ( k ⩾ j ) f_{i,j}=\max\{f_{i,k}\}(k\geqslant j) fi,j=max{fi,k}(k⩾j)。
那有用的状态似乎就只有
n
2
n^2
n2 个了。
(就小于的位置不用,模了有变化的就模)
(或者让这个位置作为
a
i
−
1
a_i-1
ai−1 的位置,然后你就在大于的时候枚举一下,让
f
i
,
j
f_{i,j}
fi,j 作为做的值)
但其实是
n
log
n
n\log n
nlogn 个状态的,因为你取模每个数最多取
log
\log
log 个就没了。
然后用
m
a
p
map
map 记录当前状态即可。
代码
#include<map>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int N = 2e5 + 100;
ll n, x;
map <ll, ll> f;
int main() {
scanf("%lld", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &x);
if (i == 1) f[x - 1] = 0;
else {
for (map <ll, ll> ::iterator it = f.lower_bound(x); it != f.end(); f.erase(it++)) {
ll now = (*it).first, val = (*it).second;
f[now % x] = max(f[now % x], val + (i - 1) * (now - now % x));
f[x - 1] = max(f[x - 1], val + (i - 1) * (((now + 1) / x * x - 1) - (x - 1)));
}
}
}
ll ans = 0;
for (map <ll, ll> ::iterator it = f.begin(); it != f.end(); it++)
ans = max(ans, n * (*it).first + (*it).second);
printf("%lld", ans);
return 0;
}
相关文章
- 【CJOJ2499】【DP合集】棋盘 chess
- 【CF917D】Stranger Trees 树形DP+Prufer序列
- 【BZOJ2164】采矿 树链剖分+线段树维护DP
- 【BZOJ3677】[Apio2014]连珠线 换根DP
- 【BZOJ1725】[Usaco2006 Nov]Corn Fields牧场的安排 状压DP
- sp dp
- POJ 3666 Making the Grade (DP)
- HDU 4597 Play Game (DP,记忆化搜索,博弈)
- 【LightOJ 1422】Halloween Costumes(区间DP)
- Holding Bin-Laden Captive!_hdu_1085(DP).java
- BZOJ 1087 SCOI2005 互不侵犯King 状压DP
- HDU 1069 Monkey and Banana(最大的单调递减序列啊 dp)
- 【uoj#22】[UR #1]外星人 组合数学+dp
- 【codevs1380】没有上司的舞会 树形dp