原題：ZOJ 3791?http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3791

題意：給定兩個0-1序列s1, s2，操作t次，每次改變m個位置，求把s1改變為s2的方法總數。
解法：

DP，s1和s2哪些位置相同并不重要，重要的是有幾個位置不同。改變的時候也一樣，改變哪些位置并不重要，重要的是改變之后有幾個位置不同。當時就想到了這一點，后面就不知道怎么辦了。

定義： dp[i][j]表示i次操作之后有j個位置不同的方法數，答案就是dp[k][0]。

對于dp[i-1][j]，經過一次操作之后假設把x個位置從不同變為相同，剩下m-x個位置從相同變為不同，那么轉移方程：

dp[i][j+m-x-x] += dp[i-1][j] * C(j, x) * C(n-j, m-x)

其中C(j, k)表示組合數，即從j個不同的位置選出k個改變。循環x即可。

代碼：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#define Mod 1000000009
#define ll long long
using namespace std;
#define N 107int c[N][N];
ll dp[N][N];void calc_C()
{memset(c,0,sizeof(c));c[0][0] = 1;for(int i=1;i<=100;i++){c[i][0] = 1;for(int j=1;j<=i;j++)c[i][j] = (c[i-1][j-1] + c[i-1][j])%Mod;}
}int main()
{int n,s,m;int dif,i,j,k;string a,b;calc_C();while(scanf("%d%d%d",&n,&s,&m)!=EOF){cin>>a>>b;dif = 0;for(i=0;i<n;i++)if(a[i] != b[i])dif++;memset(dp,0,sizeof(dp));dp[0][dif] = 1;for(i=1;i<=s;i++){for(j=0;j<=n;j++){for(k=max(0,m-n+j);k<=j&&k<=m;k++){dp[i][j+m-k-k] += ((dp[i-1][j]*c[j][k])%Mod)*c[n-j][m-k]%Mod;dp[i][j+m-k-k] %= Mod;}}}printf("%lld\n",dp[s][0]);}return 0;
}

View Code

?

轉載于:https://www.cnblogs.com/whatbeg/p/3827260.html

總結

以上是生活随笔為你收集整理的2014 Super Training #8 C An Easy Game --DP的全部內容，希望文章能夠幫你解決所遇到的問題。

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