程序師世界是廣大編程愛好者互助、分享、學習的平台，程序師世界有你更精彩！
設為首頁 加入收藏
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> zoj3791(An Easy Game) DP

zoj3791(An Easy Game) DP

編輯：C++入門知識

題意：給出兩個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; im)
            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
  1. 上一頁:
  2. 下一頁:
C++入門知識
leetcode筆記：Pow(x, n)

leetcode筆記：Pow(x, n) 一. 題目描述

zoj 2334 Monkey King/左偏樹+並查集，zoj2334

zoj 2334 Monkey King/左偏樹+並查集，z
大話設計模式C++實現-第2章-策略模式

大話設計模式C++實現-第2章-策略模式 一、UML圖

C++那些細節--typedef關鍵字

C++那些細節--typedef關鍵字   一
hdu 1085 Holding Bin-Laden Captive!，hdubin-laden

hdu 1085 Holding Bin-Laden Cap
無向圖的廣度優先搜索（采用鄰接表存儲）C++實現

  // 無向圖的廣度優先搜索（采用
相關文章
閱讀排行榜
Leetcode:signal_number_ii c++ public private protected關鍵字，privateprotected poj 3831 Open-air shopping malls HDU 4597 Play Game 記憶化搜索 HDU 1428 漫步校園(記憶化搜索) uva 11012 - Cosmic Cabbages(暴力) 字符串類習題、面試題詳解（第一篇），習題詳解 C++: Command Line Processing，lineprocessing LeetCode Partition List 高質量C++/C編程指南--類的繼承與組合 直接選擇排序
熱門圖文
php中運用http調用的GET和POST方法示例 就我不坑，不坑 Delphi 7中用Indy組件開發Socket應用程序 Log4net入門（WCF篇），log4net入門wcf 函數調用棧和棧幀 用Round函數讓四捨五入變的更精確 AspCookies常用命令簡介 和GUI有關的各種對象
欄目導航
C++基礎知識C++入門知識關於C++
Copyright © 程式師世界 All Rights Reserved