题解 CF889E 【Mod Mod Mod】

ywy_c_asm

2019-06-01 16:49:19

Solution

这题的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); } ```