题解 CF889E 【Mod Mod Mod】
ywy_c_asm
2019-06-01 16:49:19
这题的dp转移还挺有意思的。
首先一个显而易见的事实就是这个初始的数$x$不断的取模之后一直都是单调不增的,那么我们假设最后取模取到了$x_{end}$,可以考虑把这个和搞成$nx_{end}+b$的形式,换句话说我们要对于一个确定的$x_{end}$找一个最大的$b$,即大于$x_{end}$的那部分的和(可以画个图象)。
然后我们考虑$dp[i][j]$为模完$a_i$之后$x=j$时的最大的$b$,此时我们的和是$ij+b$,实际上这里就蕴含一个东西就是如果$x<j$那么$dp[i][x]<=dp[i][j]$没有任何意义,肯定不如$j$更优。那么,我们不妨就把$[0,j]$**视作一个整体**去转移,也就是说我们在$j$处考虑到$dp[i+1]$的转移时暂且假设$[0,j]$的$b$都取到了$dp[i][j]$,这样一定是合法的。**注意,现在以下所讨论的转移都假设$[0,j]$的$b$取的都是$dp[i][j]$而不是什么更大的数,如果有更大的我们一定能在$dp[i][<j]$的转移中考虑到**。但是我们肯定不可能考虑$[0,j]$里所有数模$a_{i+1}$的结果,我们有一个naive的想法是尽量让模$a_{i+1}$的结果尽量大,而$[0,j]$模$a_{i+1}$是$0,1,2,3,\cdots a_{i+1}-1,0,1,2\cdots j\%a_{i+1}$(这里我们假设$j>=a_{i+1}$,否则的话转移显然就是$dp[i+1][j]=dp[i][j]$,因为$x_{end}$并不改变,$b$也是不变的),假设$[0,j]$最后一个$\%a_{i+1}=a_{i+1}-1$的是$y$,那么考虑$[y+1,j-1]$这一段,显然就已经不用考虑和它们余数相同的比它们还要小的$[0,j]$的数了,但是既然它们后面没有模的0到$a_{i+1}-1$的循环了,那么可以给它们不断的++一直到$j$,这样自身+1,余数也+1,所以$j$一定要比$[y+1,j-1]$这一段数更优。然后我们考虑$<=y$的部分,即还没考虑的$[y-a_{i+1}+j\%a_{i+1},y]$这一段,它们也可以通过不断的+1加到$y$,所以$y$是比剩下的部分更优的,所以我们只考虑$j->j\%a_{i+1}$与$y->y\%a_{i+1}$(即$a_{i+1}-1$)这两个过程就行了,所以我们的转移方程就是:
$dp[i+1][j\%a_{i+1}]=\max\{dp[i][j]+i(j-j\%a_{i+1})\}$
这个$i(j-j\%a_{i+1})$的意思是本来现在的和是$ij+dp[i][j]$,模完之后变成了$ij+dp[i][j]+j\%a_{i+1}=(i+1)(j\%a_{i+1})+dp[i][j]+i(j-j\%a_{i+1})$。
另外还有考虑$y$的转移:
$dp[i+1][a_{i+1}-1]=\max\{dp[i][j]+ia_{i+1}(\lfloor\frac{j-(a_{i+1}-1)}{a_{i+1}}\rfloor\}$
这个类似上面的,此时$y-(a_{i+1}-1)=a_{i+1}(\lfloor\frac{j-(a_{i+1}-1)}{a_{i+1}}\rfloor$。
显然,这个dp可以用$map$滚动转移,由于每次只会凭空多一个$a_{i+1}-1$的状态,或者是$j$变成(因为$j>=a_{i+1}$,我们做完这个转移之后会把它删掉)$j\%a_{i+1}$,前者相当于有$O(n)$个起始状态,后者是一个起始状态会不断的取模变成更小的,而我们知道每次取模变成更小的会至少减半,所以总共转移的复杂度加上map是$O(n\log n\log x)$的。
上代码~
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <functional>
#define ll long long
using namespace std;
namespace ywy {
inline ll get() {
ll n = 0;
char c;
while ((c = getchar()) || 23333) {
if (c >= '0' && c <= '9')
break;
if (c == '-')
goto s;
}
n = c - '0';
while ((c = getchar()) || 23333) {
if (c >= '0' && c <= '9')
n = n * 10 + c - '0';
else
return (n);
}
s:
while ((c = getchar()) || 23333) {
if (c >= '0' && c <= '9')
n = n * 10 - c + '0';
else
return (n);
}
}
ll ints[222222];
map<ll, ll, greater<ll> > mp;
typedef map<ll, ll, greater<ll> >::iterator it;
ll tmp[1000001];
void ywymain() {
int n = get();
for (register int i = 1; i <= n; i++) ints[i] = get();
mp[ints[1] - 1] = 0;
for (register int i = 1; i < n; i++) {
int ptr = 0;
ll mx = 0;
for (it j = mp.begin(); j != mp.end(); j++) {
if ((j->first) < ints[i + 1])
break;
mp[ints[i + 1] - 1] =
max(mp[ints[i + 1] - 1],
(j->second) + (ll)i * (ints[i + 1] * (((j->first) + 1) / ints[i + 1]) - ints[i + 1]));
mp[(j->first) % ints[i + 1]] = max(mp[(j->first) % ints[i + 1]],
(j->second) + (ll)i * ((j->first) - (j->first) % ints[i + 1]));
tmp[ptr] = j->first;
ptr++;
}
while (ptr) ptr--, mp.erase(tmp[ptr]);
}
ll ans = 0;
ll mx = 0;
for (it i = mp.begin(); i != mp.end(); i++) {
ans = max(ans, n * (i->first) + (i->second));
}
cout << ans << endl;
}
}
int main() {
ywy::ywymain();
return (0);
}
```