題目鏈接：點(diǎn)擊查看

題目大意：給出兩個(gè)數(shù)n和k，要求將n分成k份，問有多少種方案數(shù)，注意：

1 1 5和1 5 1還有5 1 1算同一種方案

題目分析：因?yàn)閚只給到了200，并且k最大為6，所以直接dfs搜索就好了，注意記得剪枝，還是需要注意一下dfs對(duì)于題目的設(shè)計(jì)，還有關(guān)于模型的抽象，對(duì)于這個(gè)題目而言，可以抽象出來(lái)的模型是k個(gè)桶，我們需要像其中放置n個(gè)球，每個(gè)桶至少需要放一個(gè)，這樣我們就可以直接搜索k個(gè)桶，當(dāng)k個(gè)桶都搜索完后，就可以判斷當(dāng)前答案的合理性了，總的時(shí)間復(fù)雜度應(yīng)該是30^6，差不多7e8左右，剪枝后復(fù)雜度就小很多了

因?yàn)檫@個(gè)題目每個(gè)桶和每個(gè)球都是無(wú)差別的，所以我們?yōu)榱朔乐怪貜?fù)枚舉，可以選擇非嚴(yán)格升序枚舉，也就是讓每個(gè)桶的球都大于等于前一個(gè)桶中球的個(gè)數(shù)

代碼：

#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> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e6+100;int ans=0;void dfs(int cur,int sum,int last)//cur:當(dāng)前遍歷到第幾個(gè)桶 sum:手里還有多少個(gè)球要放 last:當(dāng)前桶里放了多少個(gè)球 {if(cur==0)//所有的桶都枚舉完畢{if(sum==0)//如果所有的球都放進(jìn)去了，方案數(shù)加一ans++;return;}for(int i=last;i<=sum/cur;i++)//非嚴(yán)格升序遞歸+剪枝，因?yàn)槭Ｓ嗟那蛉舴旁赾ur個(gè)桶里，每個(gè)桶最多放sum/cur個(gè)球dfs(cur-1,sum-i,i); }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,k;scanf("%d%d",&n,&k);dfs(k,n,1);cout<<ans<<endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的洛谷 - P1025 数的划分(dfs)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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