当前位置：网站首页>ZOJ - 4114 Flipping Game-dp,合理状态表示

ZOJ - 4114 Flipping Game-dp,合理状态表示

2022-07-25 15:23:00 【塔子哥来了】

题目大意:

给你两个长度为 n ( n ≤ 100 ) n(n \leq 100) n(n≤100)的01字符串.你需要进行 k ( k ≤ 100 ) k(k \leq 100) k(k≤100)轮操作,每次操作要选择 m ( m ≤ n ) m(m\leq n) m(m≤n)个字符，将其反转。

问你有多少种方案使得 k k k轮之后使得第一个字符串转变成第二个字符串.

题目思路:

K轮之后,两个字符串相等。那么我们只需要记录当前进行到第几轮且有几个字符串不相等即可.

所以定义 d p ( i , j ) dp(i,j) dp(i,j) 为前 i i i轮,当前局面有恰好 k k k个与第二个字符串不同的字符的方案数.

d p ( i , j − k + m − k ) + = C j k C n − j m − k d p ( i − 1 , j ) dp(i,j-k+m-k)+=C_{j}^{k}C_{n-j}^{m-k}dp(i-1,j) dp(i,j−k+m−k)+=Cjk​Cn−jm−k​dp(i−1,j)

原网站

版权声明
本文为[塔子哥来了]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_35577488/article/details/120815970

边栏推荐

猜你喜欢

随机推荐