ABC.E-DP题目集锦

发表于 2022-09-26 分类于题解

ABC266E. Throwing the Die

题意：有 $n$ 次扔骰子机会，每次随机扔到 $[1,6]$ 中的一个整数，每次扔完可以选择结束游戏（此时游戏结果为扔到的点数）或者再扔一次，求最佳策略下结果的期望。

设 $f_i$ 表示有 $i$ 次机会时的得分期望，则 $f_i$ 可以由 $f_{i-1}$ 转移而来：如果第一次扔到的值小于 $f_{i-1}$ ，那么继续游戏，答案为 $f_{i-1}$ ；如果大于 $f_{i-1}$ ，那么结束游戏，答案为当前扔到的值。

code:

#include<bits/stdc++.h>
using namespace std;
long double g[110];
int main() {
    int n;
    cin>>n;
    g[1]=3.5;
    for(int i=2;i<=n;i++)
        for(int j=1;j<=6;j++)
            g[i]+=max((long double)j,g[i-1])/6;
    printf("%.7Lf\n",g[n]);
    return 0;
}

ABC265E. Warp

题意：平面直角坐标系，一开始你在 $(0,0)$ ，每次可以从以下三种方向中选择一种移动： $(A,B),(C,D),(E,F)$ ；有 $m$ 个障碍物，第 $i$ 个位于 $(x_i,y_i)$ ，求不碰到障碍物的情况下走 $n$ 步的方案数。

$f[i][j][k]$ 表示走 $i$ 步 1 操作、 $j$ 步 2 操作， $k$ 步 3 操作的方案数，则

f[i][j][k]=\begin{cases}0,\ \ \ \ \ \ \ \ \text{if }(iA+jC+kE,iB+jD+kF)\text{ is an obstacle}\\ f[i-1][j][k]+f[i][j-1][k]+f[i][j][k-1],\ \text{ otherwise}\end{cases}

由于在每一层中 $i+j+k$ 为定值，可以优化掉一维状态 $k$ 。

code:

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int x[3],y[3];
int f[310][310];
pair<int,int> t[100010];
set<pair<int,int> > s;
int main() {
    int n,m;
    cin>>n>>m;
    for(int i=0;i<3;i++)
        cin>>x[i]>>y[i];
    for(int i=1;i<=m;i++) {
        cin>>t[i].first>>t[i].second;
        s.insert(t[i]);
    }
    f[0][0]=1;
    for(int len=1;len<=n;len++) {
        for(int i=len;i>=0;i--)
            for(int j=len-i;j>=0;j--) {
                int k=len-i-j;
                int nowx=i*x[0]+j*x[1]+k*x[2];
                int nowy=i*y[0]+j*y[1]+k*y[2];
                auto tmp=s.lower_bound(make_pair(nowx,nowy));
                if(tmp!=s.end()&&(*tmp)==make_pair(nowx,nowy)) f[i][j]=0;
                else {
                    if(i>0) (f[i][j]+=f[i-1][j])%=mod;
                    if(j>0) (f[i][j]+=f[i][j-1])%=mod;
                }
            }
    }
    int ans=0;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n-i;j++)
            (ans+=f[i][j])%=mod;
    cout<<ans<<endl;
    return 0;
}

ABC263E. Sugoroku 3

题意：有 $n$ 个格子，第 $i$ 个格子有一个 $[0,a_i]$ 的骰子，每到一个格子都会扔一次该格子的骰子，扔到几往前走几步，问走到 $n$ 的期望步数。

$f[i]$ 表示从 $i$ 到 $n$ 的期望步数，则

\begin{aligned} f[i]&=\sum\limits_{j=0}^{a_i}\frac{1}{a_i+1} (f[i+j]+1)\\ &=\frac{1}{a_i+1}(f[i]+1)+\frac{1}{a_i+1}\sum\limits_{j=1}^{a_i} (f[i+j]+1)\\ &=\frac{1}{a_i+1}f[i]+\frac{1}{a_i+1}\left(1+\sum\limits_{j=1}^{a_i} (f[i+j]+1)\right)\\ \frac{a_i}{a_i+1}f[i]&=\frac{1}{a_i+1}\left(1+\sum\limits_{j=1}^{a_i} (f[i+j]+1)\right)\\ f[i]&=\frac{1}{a_i}\left(1+\sum\limits_{j=1}^{a_i} (f[i+j]+1)\right) \end{aligned}

$\sum$ 可以使用前缀和维护。

code:

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int a[200010],inv[200010];
int f[200010],suf[200010];
int main() {
    int n;
    cin>>n;
    inv[1]=1;
    for(int i=2;i<=n;++i)
        inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    for(int i=1;i<n;i++)
        cin>>a[i];
    f[n]=suf[n]=0;
    for(int i=n-1;i>0;i--) {
        int x=(suf[i+1]-suf[i+a[i]+1]+1+mod)%mod;
        f[i]=(1ll*x*inv[a[i]]+1)%mod;
        suf[i]=(suf[i+1]+f[i])%mod;
    }
    cout<<f[1]<<endl;
    return 0;
}

ABC253E. Distance Sequence

题意：问有多少个序列 $a$ 满足 $\forall 1\le i\le n,a_i\le m$ 且 $\forall 1\le i<n,\left|a_{i+1}-a_i\right|\ge K$

$f[i][j]$ 表示考虑前 $i$ 位，第 $i$ 位为 $j$ 的方案数，则

f[i][j]=\sum\limits_{k=1}^{j-K} f[i-1][k]+\sum\limits_{k=j+K}^m f[i-1][k]

可以使用前缀和维护。

code

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,m,k,f[1010][5010];
int s[5010];
int main() {
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
        f[1][i]=1,s[i]=(s[i-1]+f[1][i])%mod;
    for(int i=2;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            f[i][j]=((s[max(j-k,0)]+s[m])%mod-s[min(j+k-1,m)]+mod)%mod;
            if(!k) f[i][j]=(f[i][j]-f[i-1][j]+mod)%mod;
        }
        for(int j=1;j<=m;j++)
            s[j]=(s[j-1]+f[i][j])%mod;
    }
    cout<<s[m]<<endl;
    return 0;
}

ABC251E. Takahashi and Animals

题意：有 $n$ 个动物，每次操作可以花费 $a_i$ 的代价投喂第 $i$ 和 $i+1$ 个动物（特殊地，可以花费 $a_n$ 的代价投喂第 $n$ 和第 $1$ 个动物）。求喂完每个动物至少一次的最小代价。

$f[i][0/1][0/1]$ 表示考虑前 $i$ 个动物，第 $1$ 个动物选/不选，第 $i$ 个动物选/不选的最小代价，则

\begin{cases} f[i][j][0]=f[i-1][j][1]\\ f[i][j][1]=min(f[i-1][j][0],f[i-1][j][1])+a_i \end{cases}

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[600010],f[600010][2][2];
signed main() {
    int n,ans=1e18;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    f[1][1][1]=a[1],f[1][0][0]=0;
    f[1][1][0]=f[1][0][1]=1e18;
    for(int i=2;i<=n;i++) {
        for(int j=0;j<=1;j++) {
            f[i][j][1]=min(f[i-1][j][0],f[i-1][j][1])+a[i];
            f[i][j][0]=f[i-1][j][1];
        }
    }
    cout<<min({f[n][1][0],f[n][0][1],f[n][1][1]})<<endl;
    return 0;
}

ABC249E. RLE

对于一个小写字母组成的字符串 $S$ ，可以如下生成一个字符串 $T$ ：将 $S$ 中每个极长的同字符子串替换为“字符+字符个数”的形式。例如 $S=\texttt{aaabcc}$ 生成 $T=\texttt{a3b1c2}$ 。求有多少个长度为 $n$ 的字符串 $S$ 满足 $len_T<len_S$ 。

$f[i][j]$ 表示 $S$ 的长度为 $i$ ， $T$ 的长度为 $j$ 的方案数，则

f[i][j]=(26-1)\sum\limits_{k\le i}f[i-k][j-\log_{10}(k)]

转化一下求和方式：

f[i][j]=(26-1)\sum\limits_{k\le\log_{10}i} \sum\limits_{10^{k-1}\le l<10^k}f[i-l][j-k]

其中第二个 $\sum$ 可以使用前缀和维护。复杂度 $n^2\log n$ 。

code