设为首页 加入收藏

TOP

zoj3791(An Easy Game) DP
2015-07-24 06:53:59 来源: 作者: 【大 中 小】 浏览:57次
Tags：zoj3791 Easy Game

题意：给出两个01字符串s1,s2.每次改变s1上m个位置的字符。问k步之后使得s1变为s2的方法有多少种。


解法：DP，关键是状态的设计。考虑还是唯一性和可传递性。dp[i][j]表示第i步后有j个不同到目标的走法数。记忆化搜索dp[0][dif](dif表示初始时不同字符的个数)。转移时候枚举选择情况即可。


代码：

/******************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              #include 
             
               //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 const double pi=acos(-1.0); typedef long long LL; const int Max=110; const int INF=1000000009; int n,k,m; string s1,s2; LL C[Max][Max]; int init() { for(int i=0; i
              
               m) break; ans=(ans+(C[num][i]*C[n-num][m-i])%INF*dfs(step+1,num-i+m-i))%INF; } return dp[step][num]=ans; } int main() { init(); while(scanf("%d%d%d",&n,&k,&m)==3) { dif=0; memset(dp,-1,sizeof dp); cin>>s1>>s2; for(int i=0; i
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：UVA 297 Quadtrees（四叉树建树、.. 下一篇：HDU - 4815 Little Tiger vs. Dee..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: