#动态规划#CF889E Mod Mod Mod

题目传送门

分析

这道题有一个很妙的地方就是将一段前缀整体一起做。

设 \(dp[i][j]\) 表示\(x\) 被前 \(i\) 个数取模后答案最大，并且 \(j\) 为取得此答案的最大值

最后再对 \(dp[i][j]+n*j\) 取最大值即可。

如果 \(j\) 被 \(a_i\) 取模之后仍然保留 \(j\)，那么 \(dp[i][j\bmod a_i]=\max\{dp[i-1][j]+(j-j\bmod a_i)*(i-1)\}\)

如果不保留 \(j\)，那么 \(dp[i][a_i-1]=\max\{dp[i-1][j]+\left\lfloor \frac{j-(a_i-1)}{a_i}\right\rfloor*a_i*(i-1)\}\)

然后取模之后会减半，所以时间复杂度为 \(O(n\log n\log a_i)\)

代码

#include 
#include 
#include 
#include 
using namespace std;
const int N=200011;
typedef long long lll;
mapdp; lll n,a[N],ans;
map::iterator it;
lll iut(){
    lll ans=0; char c=getchar();
    while (!isdigit(c)) c=getchar();
    while (isdigit(c)) ans=ans*10+c-48,c=getchar();
    return ans;
}
int main(){
    n=iut();
    for (int i=1;i<=n;++i) a[i]=iut();
    dp[a[1]-1]=0;
    for (int i=2;i<=n;++i){
        for (it=dp.lower_bound(a[i]);it!=dp.end();dp.erase(it++)){
            lll x=it->first,y=it->second,t0=dp[x%a[i]],t1=dp[a[i]-1];
            if (t0first,y=it->second;
        if (ans
DP-线性、区间、树形、状压dp

相关

标签