The solution of P3012

发布时间 2023-09-30 11:44:26作者: feather_life

problem & blog


很明显是个 DP。

于是我们定义 \(dp_{i,j,k}\) 为末尾的字符的 ASCII 码为 \(i\),有 \(j\) 个大写字母,\(k\) 个小写字母。

然后在枚举能接在 \(i\) 之后所有字母即可。

然后考虑 \(dp_{i,j,k}\) 给后面的 DP 值得贡献。

所以就有:

\[dp_{\text{能接在i后面的字母},j + 1,k} += dp_{i,j,k} \text{(能接在i后面的字母为大写字母)} \]

\[dp_{\text{能接在i后面的字母},j,k + 1} += dp_{i,j,k} \text{(能接在i后面的字母为小写字母)} \]


code