【题解】AT2022 [ARC059D] Unhappy Hacking

dd_d · 2021-09-10 16:34:09 · 题解

更好的阅读体验

Sol

考虑 dp。
设 dp_{i,j} 表示敲击了键盘 i 次，匹配了 j 个字符的方案数。
考虑如何转移。
分以下两种情况进行讨论。

• 敲了退格。那么 dp_{i,j} 可以由 dp_{i-1,j+1} 转移。由于我们不关心第 j+1 位的字符是 0 还是 1，所以 dp_{i,j}=dp_{i,j}+2 \times dp_{i-1,j+1}。
• 敲了 0 或 1。那么 dp_{i,j} 可以从 dp_{i-1,j-1} 转移而来。但要注意，此处 j-1 需 \geq 0。

边界 dp_{0,0}=1。

Code

cin>>n>>st;
dp[0][0]=1;
for (int i=1;i<=n;i++)
    for (int j=0;j<=i;j++)
        dp[i][j]=(dp[i-1][max(j-1,0)]+dp[i-1][j+1]*2%mod)%mod;
cout<<dp[n][st.size()]<<endl;