小明被劫持到X賭城，被迫與其他3人玩牌。

一副撲克牌（去掉大小王牌，共52張），均勻發(fā)給4個人，每個人13張。

這時，小明腦子里突然冒出一個問題：

如果不考慮花色，只考慮點數(shù)，也不考慮自己得到的牌的先后順序，自己手里能拿到的初始牌型組合一共有多少種呢？

---

題目分析：又是被zx學長秒穿的一道題目，一開始我抽象出來的模型就不對，導致設計出來的算法超時，無法跑出正確答案，我抽象出來的模型是52張牌，隨便選13個，就寫了個dfs去跑，很顯然是超時的

正確的模型應該是13個桶，每個桶中有4張牌，我們應該依次從桶中摸牌，不重不漏

模型抽象出來了，dfs就比較好設計了，當我們面對這一個桶的時候，可以摸的牌有五種選擇：

不摸

摸1張

摸2張

摸3張

摸4張

然后一直往下dfs就好了。。時間復雜度是5的(13-13/4)=10次方，大概也才1e7，增加了各種剪枝和特判之后，在本地差不多兩三秒就跑出來了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int ans=0;void dfs(int pos,int num)//pos:當前到了第幾個桶 num:現(xiàn)在手里有多少張牌 {if(num==13)//如果滿足條件，答案加一{ans++;return;}if(num>13)//如果越界，直接返回return;if(pos==13)//同上return;for(int i=0;i<=4;i++)//五種情況爆搜dfs(pos+1,num+i); }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);dfs(0,0);cout<<ans<<endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的蓝桥杯 - 牌型种数(dfs)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。