AT_dp

发表于2024-03-31|更新于2024-07-01

|字数总计:5.2k|阅读时长:23分钟|阅读量:

闲话

DP 太菜了，刷 AT 经典 DP，前面的比较简单，从 J 开始吧 qwq

AT_dp_J

期望 DP

注意到 $a_i\leq3$，所以状态应该跟 $a_i$ 有关。考虑设 $f_{a,b,c,d}$ 表示有 $a$ 种剩余 $3$ 个的寿司，$b$ 种剩余 $2$ 个的寿司……

$$f_{a,b,c,d}=1+\frac{a}{n}f_{a-1,b+1,c,d}+\frac{b}{n}f_{a,b-1,c+1,d}+\frac{c}{n}f_{a,b,c-1,d+1}+\frac{d}{n}f_{a,b,c,d}$$
整理并可得
$$f_{a,b,c,d}=\frac{n}{n-d}+\frac{a}{n-d}f_{a-1,b+1,c,d}+\frac{b}{n-d}f_{a,b-1,c+1,d}+\frac{c}{n-d}f_{a,b,c-1,d+1}$$

这样是四维的，发现 $d=n-(a+b+c)$，于是变成 $3$ 维，可以 $O(n^3)$ 的 DP，得到最终方程

$$f_{a,b,c}=\frac{n}{a+b+c}+\frac{a}{a+b+c}f_{a-1,b+1,c}+\frac{b}{a+b+c}f_{a,b-1,c+1}+\frac{c}{a+b+c}f_{a,b,c-1}$$

Code:

cin>>n;
for(int i=1,x;i<=n;++i) cin>>x,a[x]++;
for(int i=0;i<=n;++i)
      for(int j=0;j<=n;++j)
        for(int k=0;k<=n;++k)
          if(i+j+k){
            double p=i+j+k;
            if(i) f[i][j][k]+=(1.0*i/p*f[i-1][j+1][k]);
            if(j) f[i][j][k]+=(1.0*j/p*f[i][j-1][k+1]);
            if(k) f[i][j][k]+=(1.0*k/p*f[i][j][k-1]);
            f[i][j][k]+=1.0*n/p;
          }
cout<<fixed<<setprecision(10)<<f[a[3]][a[2]][a[1]]<<endl;

给点启示： DP 优化的一个思路：合并等价状态、消除无用状态（这个有点像百钱买百只因）。

AT_dp_K

博弈论

简单题。设 $f_i$ 表示剩余 $i$ 个石子时当前操作者的胜负，那么显然 $f_0=0$。考虑转移，用点博弈论的知识，必败状态后继的所有状态都是必胜状态，那么写出转移 $f_i=\max{[f_{i-a_j}=0],1\le j\le n}$

Code:

for(int i=1;i<=k;++i){
    for(int j=1;j<=n;++j){
        if(i-a[j]<0) continue;
        f[i]|=(!f[i-a[j]]);
      }
}

AT_dp_L

区间 DP

一个经典的 trick。设 $f_{i,j}$ 表示序列还剩下 $[i,j]$ 时，$X-Y$ 的最大值。转移要分两种情况，因为是两个人轮流取，一个会使答案增大，另一个使答案变小。

具体地，当前操作次数为偶数，先手取改变 $X$，$f_{i,j}=\max(f_{i+1,j}+a_i,f_{i,j-1}+a_j)$。

否则后手取，$f_{i,j}=\min(f_{i+1,j}-a_i,f_{i,j-1}-a_j)$。

答案即为 $f_{1,n}$，时间复杂度 $O(n^2)$。

与此题很类似的，还有 AT_tdpc_game，可以左转我的题解。

Code:

for(int len=1;len<=n;++len){
    for(int i=1;i+len-1<=n;++i){
        int j=i+len-1;
        if((n-len)&1) f[i][j]=min(f[i+1][j]-a[i],f[i][j-1]-a[j]);
        else f[i][j]=max(f[i+1][j]+a[i],f[i][j-1]+a[j]);
    }
}

此题还有一个贪心的思路，可以做到线性。

考虑对于每三个数，如果中间的最大，那么一定是先手取两边，后手取中间，这样把序列中的这样结构的三个数贡献合并成两边减中间，此时序列一定先减后增，直接贪心即可。

形式化地，$\forall a_{i-1},a_i,a_{i+1}(1<i<n)，s.t.\ a_i\ge a_{i-1}$ 且 $a_i\ge a_{i+1}$，将其改为 $f_i=a_{i-1}+a_{i+1}-a_i$，剩余的不变。

这个做法代码不贴了。

启示： 很多这种类似博弈两个人取数的题都可以转化成这种 DP 的状态设计，算是一个区间 DP 的套路了。

AT_dp_M

前缀和优化 DP

首先考虑一下朴素 DP，设 $f_{i,j}$ 表示进行到 $i$，已经分出去了 $j$ 块糖的方案数。那么显然 $f_{i,j}=\sum_{k=0}^{a_i}f_{i-1,k}$。每次转移都需要扫一遍，时间复杂度 $O(nk^2)$ 。

但是发现每一层 DP 的状态只与上一层有关，所以可以直接使用前缀和优化，时间复杂度 $O(nk)$。

代码不贴了，注意数组下标，前缀和容易 RE。

启示： 当发现 DP 转移时方程只与上一层有关时，可以考虑用一些求和数据结构优化（比如前缀和）。

AT_dp_N

区间 DP
前缀和优化 DP

区间 DP 傻题，和石子合并一模一样。

需要注意的一点是，朴素直接计算贡献是 $O(n^4)$ 的，使用前缀和优化到 $O(n^3)$。

Code:

for(int i=n;i>=1;--i)
    for(int j=i+1;j<=n;++j)
          for(int k=i;k<j;++k)
              f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);

AT_dp_O

状压 DP

~~拜谢老头。~~ 看数据范围考虑状压 DP。发现一个合法的方案一定满足每一行、每一列只选一个 $1$，所以设 $f_{i,S}$ 表示进行到第 $i$ 行，此时选点集合为 $S$，复杂度 $O(n^22^n)$ 会 T 掉。但观察可知已知 $S$ 即可确定 $i$，是 $S$ 中 $1$ 的个数，所以可以直接设为 $f_S$，复杂度 $O(n2^n)$。

Tips：popcount 用来计算二进制 $1$ 的个数。

Code:

f[0]=1;
for(int S=0;S<(1<<n);++S){
    int k=__builtin_popcount(S);
    for(int j=0;j<n;++j){
        if(!(S&(1<<j))&&a[k][j])
            f[S|(1<<j)]=(f[S|(1<<j)]+f[S])%mod;
    }
}

AT_dp_P

树形 DP

~~没有舞会的上司。~~ 树上 DP 简单题。设 $f_{u,0/1}$ 表示当前点为 $u$，当前点是否染成黑色。那么对于 $f_{u,0}$，它的子节点染成什么颜色对其没有限制，所以 $f_{u,0}=\prod_{v\in u}(f_{v,0}+f_{v,1})$；而对于 $f_{u,1}$，子节点不能还是黑色，所以 $f_{u,1}=\prod_{v\in u}f_{v,1}$。

最后自底向上 dfs 即可，答案为 $f_{1,0}+f_{1,1}$，线性复杂度。

Code:

void dfs(int u,int fa){
    f[u][0]=f[u][1]=1;
    for(int v:e[u]){
        if(v==fa) continue;
        dfs(v,u);
        f[u][0]=f[u][0]*(f[v][0]+f[v][1])%mod;
        f[u][1]=f[u][1]*f[v][0]%mod;
    }
}

AT_dp_Q

数据结构优化 DP

最长上升子序列加权版。

发现朴素的 DP 就是朴素的 LIS，设 $f_i$ 表示以 $i$ 为结尾的最大答案，只是把每次的贡献从 $1$ 变成 $a_i$ 了。但这样做是 $O(n^2)$ 的，考虑每次都是选择 $h_j<h_i$ 的最大 $f_j$，这样可以使用数据结构优化。$f_i=a_i+\max{f_j,1\le j<i,h_j<h_i}$。需要支持单点修，区间求最值，复杂度 $O(n\ logn)$。

这里使用了树状数组，因为要求的是前缀最大值，而且单点修改，树状数组比线段树更容易实现。

Code:

树状数组部分

void add(int x,ll k){
    for(int i=x;i<=n;i+=lowbit(i)) c[i]=max(c[i],k);
}
ll query(int x){
    ll res=0;
    for(int i=x;i;i-=lowbit(i)) res=max(res,c[i]);
    return res;
}

主函数部分

for(int i=1;i<=n;++i){
    ll x,a;
    cin>>a;
    x=query(h[i]-1)+a;
    ans=max(ans,x);
    add(h[i],x);
}

启示： 对于一个 DP 转移方程，如果转移复杂度很高，要求的东西只与之前的值有关，可以尝试数据结构优化。

AT_dp_R

矩阵加速 DP

题目要求路径长度为 $k$ 的路径数，朴素的 DP 是直接设 $f_{k,i,j}$ 表示从 $i$ 到 $j$ 路径长度为 $k$ 的方案数，然后转移
$$f_{k,i,j}=\sum_{u=1}^nf_{k-1,i,u}+f_{1,u,j}$$

发现这样转移复杂度会爆炸，因为 $k$ 是 $10^{18}$ 量级的，但是这个方程你会发现跟最短路中的 Floyd 非常像，这就是个显然的矩阵乘法形式，于是想到矩阵优化，对于每一个距离矩阵 $f_i$，$f_i=f_{i-1}\times f_1$，那么直接快速幂即可，答案为 $f_1^{k}$ 的所有元素和。时间复杂度 $O(n^3\ logk)$，可以通过。

Code:

struct matrix{
    ll a[N][N];
    matrix(){memset(a,0,sizeof(a));}
}a;
matrix operator * (const matrix&a,const matrix&b){
    matrix res;
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            for(int k=0;k<n;++k)
                res.a[i][j]=(res.a[i][j]+a.a[i][k]*b.a[k][j]%mod)%mod;
    return res;
}
matrix ksm(matrix a,ll k){
    matrix res;
    for(int i=0;i<n;++i) res.a[i][i]=1;
    while(k){
        if(k&1) res=res*a;
        a=a*a;
        k>>=1;
    }
    return res;
}

启示： 当一个线性 DP 发现转移数量非常多（一般达到了 $10^9$ 以上的量级），可以考虑矩阵优化。

AT_dp_S

数位 DP

看数据范围超级大想数位 DP。考虑记录 $3$ 个状态：当前位、是否达到最高位限制、当前数各位和模 $D$ 结果，边界条件是最后模 $D$ 为 $0$ 了答案加一。

具体地，设 $f_{pos,m,limit}$ 表示当前考虑到第 $pos$ 位（倒序从最高位往后找），各个位上的和模 $D$ 为 $m$，是否顶到上界。边界条件 $f_{0,0,0/1}=1$，转移时
$$f_{pos,m,limit}=\sum f_{pos-1,(m+i)%D,limit&&[i=n]}$$

注意，$i$ 表示当前枚举的下一位，$n$ 表示下一位的最大值。

警钟： 最后的答案要 -1，因为 $0$ 不算，但减一以后可能会变成负数（全为 $0$ 的情况），所以还要加 mod 再对 mod 取模。

代码用记忆化搜索实现（因为太菜了不会递推），其实 $f$ 的第三维 $limit$ 可以不用设，但为了清晰还是写了。

Code:

记忆化搜索部分

int dfs(int pos,int m,int limit){
    if(pos==0) return (m==0);
    if(~f[pos][m][limit]) return f[pos][m][limit];
    int n=limit?a[pos]:9,res=0;
    for(int i=0;i<=n;++i) res=(res+dfs(pos-1,(m+i)%d,limit&&(i==n)))%mod;
    return f[pos][m][limit]=res;
}

主函数部分

int l=strlen(s);
for(int i=0;i<l;++i) a[l-i]=s[i]-'0';
memset(f,-1,sizeof(f));
cout<<(dfs(l,0,1)-1+mod)%mod;

启示： 当计算某些数的数量，且范围很大，考虑数位 DP，记忆化搜索可以便捷实现，注意是否要考虑前导零。

AT_dp_T

前缀和优化 DP

考虑设 $f_{i,j}$ 表示确定前 $i$ 个数，其中第 $i$ 个是 $j$ 的方案数，那么初始状态 $f_{1,1}=1$。对于转移分两种情况讨论，如果 $s_i$ 是小于号，那么 $f_{i,j}=\sum_{k=1}^{j-1}f_{i-1,k}$，否则 $f_{i,j}=\sum_{k=j}^{i-1}f_{i-1,k}$。

朴素的转移是 $O(n^3)$ 的。发现又是只与上一层状态有关，可以通过前缀和优化为 $O(n^2)$，于是可以通过此题。

注意一下大于小于号与下标对应关系 qwq。

Code:

f[1][1]=s[1][1]=1;
for(int i=2;i<=n;++i){
    for(int j=1;j<=i;++j){
        if(ch[i]=='<') f[i][j]=s[i-1][j-1]%mod;
        else f[i][j]=(f[i][j]+s[i-1][i-1]-s[i-1][j-1]+mod)%mod;
        s[i][j]=(s[i][j-1]+f[i][j])%mod;
    }
}
for(int i=1;i<=n;++i) ans=(ans+f[n][i])%mod;

启示： 与 $M$ 题相同。

AT_dp_U

状压 DP

看数据范围，显然是状压。考虑设 $f_S$ 表示已选兔子集合状态为 $S$ 的答案，设 $V_T$ 表示一组中的兔子状态为 $T$ 的贡献，那么可以写出转移方程 $f_S=\max_{T\in S}{f_T+V_{\complement_ST}}$。

那其实就做完了，先枚举集合并预处理数组 $V$，复杂度 $O(2^nn^2)$，然后枚举子集转移，复杂度 $O(3^n)$，于是做完了。

Code:

for(int s=1;s<(1<<n);++s){
    for(int i=0;i<n;++i){
        for(int j=i+1;j<n;++j){
            if(((s>>i)&1)&&((s>>j)&1)){
                v[s]+=a[i][j];
            }
        }
    }
    f[s]=v[s];
}
for(int s=1;s<(1<<n);++s){
    for(int cs=s;cs>0;cs=(cs-1)&s){
        f[s]=max(f[s],f[cs]+v[s^cs]);
    }
}

启示： 枚举子集复杂度 $O(3^n)$，数据范围在 $20$ 以内有限考虑状压 DP。

AT_dp_V

树形 DP
换根 DP

考虑树形 DP。设 $g_u$ 表示 $u$ 染成黑点，$u$ 的子树内的答案，转移的话可以 $g_u=\prod_{v\in u}(g_v+1)$，表示对于每个儿子 $v$，都计算 $v$ 子树内的答案 $g_v$，以及 $v$ 染成白色，其子树全是白色的 $1$。这样总体做下来一次是 $O(n)$ 的。

但是题目要求输出每一个点为根的答案，一次 dfs 只能计算一个点为根的答案，总体复杂度 $O(n^2)$ 不能接受，所以考虑使用换根 DP，在第二次 dfs 中求出所有点的答案。

所以考虑设 $f_u$ 表示将 $u$ 染成黑色，$u$ 和其子树外的点所得的答案，那么显然对于每个点，最终的答案就是 $f_u\times g_u$。转移方程为 $f_v=f_{u}+\frac{g_{u}}{g_v+1}+1$。这表示父亲 $u$ 的答案加上 $u$ 除 $v$ 的儿子的答案再加上白点的 $1$。时间复杂度 $O(n)$。

本来这个题已经快乐地做完了，但问题在于答案需要取模，模数不一定是质数。这就十分棘手，因为你无法直接算逆元。所以考虑对于每个点 $u$ 记一个前缀积 $pre$ 和后缀积 $suf$，在第一遍 dfs 中预处理。这样转移时除法就变成了挖去此点的前后缀积。

形式化地，$f_v=f_u+pre_{u,i-1}\times suf_{u,i+1}+1$。其中 $i$ 表示 $v$ 是第几个儿子。代码中因为前后缀积的下标从 $0$ 开始，所以变成了 $pre_{u,i-2}\times suf_{u,i}$，本质上没有区别。

Code:

注意开 long long 和特殊的 $f_1=1$。

void dfs1(int u,int fa){
    g[u]=1;
    for(int v:e[u]){
        if(v==fa) continue;
        dfs1(v,u);
        g[u]=g[u]*(g[v]+1)%mod;
        pre[u].push_back(g[v]+1);
        suf[u].push_back(g[v]+1);
    }
    int l=pre[u].size();
    for(int i=1;i<l;++i) pre[u][i]=1ll*pre[u][i-1]*pre[u][i]%mod;
    for(int i=l-2;i>=0;--i) suf[u][i]=1ll*suf[u][i+1]*suf[u][i]%mod;
}
void dfs2(int u,int fa){
    int l=pre[u].size(),cnt=0;
    for(int v:e[u]){
        if(v==fa) continue;
        cnt++;
        if(l==1) f[v]=f[u]+1;
        else if(cnt==1) f[v]=f[u]*suf[u][1]%mod+1;
        else if(cnt==l) f[v]=f[u]*pre[u][cnt-2]%mod+1;
        else f[v]=f[u]*pre[u][cnt-2]%mod*suf[u][cnt]%mod+1;
        dfs2(v,u);
    }
}

启示： 换根 DP 的套路。

$1.$ 指定某个节点为根节点（一般为 $1$）。

$2.$ 第一次搜索完成预处理，同时得到该节点的解。

$3.$ 第二次搜索进行换根 DP，由已知节点推出相邻节点。

AT_dp_W

数据结构优化 DP

跟 NOIP T4 有点像对吧。先用一个经典的 trick，把一段区间的贡献转化为右端点的贡献，排序后只有到右端点才计算贡献，用一个结构体存储区间信息。

设 $f_{i,j}$ 表示进行到位置 $i$，最后一个 $1$ 在位置 $j$ 的答案。考虑转移，如果 $i=j$，也即在最后一个位置放了 $1$，那么 $f_{i,i}=\max_{j=1}^{i-1}f_{i-1,j}$。

否则 $i\neq j$，考虑每一个转移相对于 $i-1$ 都是加上了右端点在 $i$ 且左端点包含 $j$ 的答案。
$$f_{i,j}=f_{i-1,j}+\sum_{l_k\le j,r_k=i} a_k$$

这样朴素转移复杂度是 $O(n^2)$ 的，必须优化。考虑当 $i=j$，查询了最值，对于 $i\neq j$，所有右端点 $i$ 的区间贡献都要累加到 DP 数组里，这是区间加的操作。于是可以使用线段树维护 DP 数组优化一下转移，这样的复杂度变成了 $O(n\ log n)$。

空间复杂度部分，可以直接压到一维。注意每次的答案要与 $0$ 取 $\max$。

Code:

线段树部分就不放了，纯板子，查询是查询整体最值。

代码中的 $v_i$ 表示第 $i$ 个命令。

for(int i=1;i<=n;++i){
    update(1,i,i,query());
    for(auto u:v[i]) update(1,u.l,i,u.w);
}

AT_dp_X

背包 DP

我们先考虑最优策略。对于两个物品 $i$，$j$，如果 $i$ 放到 $j$ 下面，那么 $i$ 上面除了 $j$ 以外还能放 $s_i-w_j$ 重量的物品；如果 $j$ 放到 $i$ 下面，就能放 $s_j-w_i$ 重量的物品。考虑上面能放的更多那就更优，即 $i$ 放 $j$ 下面当且仅当 $s_i-w_j>s_j-w_i$，移项得 $s_i+w_i>s_j+w_j$。所以我们根据 $s+w$ 排序，这样放一定最优。

接下来 01 背包即可，答案为 $\max{f_i}$。

bool cmp(node a,node b){
    return a.w+a.s<b.w+b.s;
}
int f[20005];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i].w>>a[i].s>>a[i].v;
    sort(a+1,a+1+n,cmp);
    memset(f,-0x3f,sizeof(f));    
    f[0]=0;
    for(int i=1;i<=n;++i){
        for(int j=a[i].s;j>=0;--j){
            f[j+a[i].w]=max(f[j+a[i].w],f[j]+a[i].v);
        }
    }
    int ans=0;
    for(int i=0;i<=20000;++i) ans=max(ans,f[i]);
    cout<<ans<<endl; 
    return 0;
}

AT_dp_Y

组合数学
DP

H 题的加强版。

考虑设 $f_{i,j}$ 表示从 $(1,1)$ 走到 $(i,j)$，不经过障碍的方案数。先考虑没有障碍的简单情况，那么方案数就是 $\large \binom{i+j-2}{i-1}$，即选择 $i-1$ 步向下，剩下的向右。那么想想有障碍的转移，发现走到一个点的方案等于上述组合数减所有其左上角障碍的 $f$。想想为什么，因为所有会经过障碍的路都在左上角的障碍的 $f$ 里面。形式化地，$f_{i,j}=calc(i,j)-\sum_{x<=i,y<=j,(x,y)\ne(i,j)}calc(x,y)$。这里的 $calc$ 就是指带入上面的组合数公式。所以处理一下组合数，时间复杂度 $O(n^2)$。

pair<int,int> a[M];
ll ksm(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
ll f[M],fac[N<<1],inv[N<<1];
void init(){
    fac[0]=inv[0]=1;
    for(int i=1;i<=2e5;++i) fac[i]=fac[i-1]*i%mod;
    inv[200000]=ksm(fac[200000],mod-2);
    for(int i=2e5-1;i>=1;--i) inv[i]=inv[i+1]*(i+1)%mod;
}
ll C(ll n,ll m){
    if(n==0||m==0) return 1;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>h>>w>>n;
    init();
    for(int i=1;i<=n;++i) cin>>a[i].fi>>a[i].se;
    n++;
    a[n]=make_pair(h,w);
    sort(a+1,a+1+n);
    for(int i=1;i<=n;++i){
        f[i]=C(a[i].fi+a[i].se-2,a[i].fi-1);
        for(int j=1;j<i;++j){
            if(a[j].se>a[i].se) continue;
            f[i]=(f[i]-f[j]*C(a[i].fi-a[j].fi+a[i].se-a[j].se,a[i].fi-a[j].fi)%mod+mod)%mod;
        }
    }
    cout<<f[n]<<endl;
    return 0;
}

AT_dp_Z

斜率优化 DP

a，b 题加强版。转移显然，设 $f_i$ 表示走到 $i$ 时的最小花费，那 $f_i=\min_{1\le j<i}(f_j+(h_i-h_j)^2+C)$。

拆开式子变成 $f_i=f_j+h_i^2+h_j^2-2\times h_i\times h_j+C$。

移项，把 $j$ 分离，$f_j+h_j^2=f_i-h_i^2-C+2\times h_i\times h_j$。

设 $y_j=f_j+h_j^2$，$k_i=2\times h_i$，$x_j=h_j$，$b_i=f_i-h_i^2$，变成了一次函数形式，可以斜率优化。

题目要求最小值，维护下凸壳，又发现了 $y_j$ 和 $x_j$ 保证单调递增，所以使用单调队列维护，线性。

斜率优化可以左转我的斜率优化详解

double y(int i){
    return f[i]+h[i]*h[i];
}
double calc(int i,int j){
    return (y(i)-y(j))/(h[i]-h[j]);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>c;
    for(int i=1;i<=n;++i) cin>>h[i];
    he=t=1;
    q[1]=1;
    for(int i=2;i<=n;++i){
        while(he<t&&calc(q[he],q[he+1])<=2*h[i]) he++;
        int j=q[he];
        f[i]=f[j]+(h[i]-h[j])*(h[i]-h[j])+c;
        while(he<t&&calc(q[t-1],q[t])>=calc(q[t],i)) t--;
        q[++t]=i;
    }
    cout<<f[n]<<endl;
    return 0;
}

至此，26 个 AT_dp 已经结束，这其中几乎包含了所有比较简单的 DP 类型，获益匪浅。

完结撒花！

文章作者: JKY

文章链接: http://example.com/2024/03/31/AT_dp/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 kketchup的小窝！

相关推荐

数据库加载中