翻硬幣

jzoj 3921

題目大意：

給你一個長度為$n$的當前01串和目標01串，現在你要做$m$此操作，每次操作你要使$k$個不同的位取反，現在問你有多少種方法可以使當前01串變為目標01串

輸入樣例：

3 2 1 100 001

輸出樣例：

2

樣例解釋：

$100?>101?>001$
$100?>000?>001$

數據范圍

對于30% 的數據，$N<=4;,0<=K<=5$
對于60% 的數據，$N<=10$
對于100% 的數據，$1<=N<=100;,0<=K<=100,0<=M<=N$

解題思路：

我們設$f_{i,j}$為第$i$次操作，與目標操作有$j$位不同的種數
當$j?k$時（$j<k$的情況見代碼）
我們從$f_{i?1,j}$轉移到$f_{i,k}$首先一定要取反$j?k$次
多余的$m?(j?k)$平分成與結果相同的和不同的來取反
這樣我們就得出了狀態轉移方程：
$$f_{t,j}=f_{t,j}+f_{t?1,i}?C_i^{\frac{m?(j?k)}{2}}?C_{n?i}^{j?i+(\frac{m?(j?k)}{2})}(j?k)$$
注：代碼中的變量有所不同

代碼:

5

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define abs(x) (x) < 0? -(x) : (x) #define ll long long #define wyc 1000000007//%%% using namespace st d; ll n, m, k, s, C[150][150], f[150][150]; string str, str1; int main() {for (int i = 0; i <= 100; ++i)C[i][0] = 1;for (int i = 1; i <= 100; ++i)for (int j = 1; j <= 100; ++j)C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % wyc;//求組合數scanf("%lld%lld%lld", &n, &k, &m);cin>>str;cin>>str1;for (int i = 0; i < n; ++i)s += (str[i] != str1[i]);if (s&1 && !(m&1))//偶數無法拼成基數{printf("0");return 0;}f[0][s] = 1;for (ll t = 1; t <= k; ++t)for (ll i = 0; i <= n; ++i)for (ll j = max((i + m) & 1, i - m); j <= min(n, i + m); j += 2)//一些小優化if ((i + j + 1)&1 && abs(i - j) <= m)//也是一些小優化{if (j >= i)f[t][j] = (f[t][j] + f[t - 1][i] * C[i][((m - (j - i)) >> 1)] % wyc * C[n - i][j - i + ((m - (j - i)) >> 1)] % wyc) % wyc;//狀態轉移else f[t][j] = (f[t][j] + f[t - 1][i] * C[i][i - j + ((m - (i - j)) >> 1)] % wyc * C[n - i][((m - (i - j)) >> 1)] % wyc) % wyc;//反過來}printf("%lld", f[k][0]);return 0; }

總結

以上是生活随笔為你收集整理的【DP】翻硬币（jzoj 3921）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。