啊呀呀终于有时间写博客啦,题解呢,只有在这里才能水一水，所以以后要抓紧时间水啦(今天太困了就不水了)
懒得复制粘贴了,点这里跳转.
dfs.
选数.从第一个数开始枚举,一直枚举到第n个,每个从1个开始放,到放n个.然后判断和是不是等于m就可以啦
这个problem让人很讨厌.因为你的判断中不能直接÷3，也不能判断每两个数是否相等,因为1 1 1就是一个反例.
那么,问题来了，怎么判断重复呢?
方法就是让这些数必须为升序,举个栗子:
1 1 5
1 5 1
5 1 1
因为1 5 1不是升序排除,151排除,511排除
则只剩下1 1 5 解决问题.（想了1year）
思路想完了那就上代码吧:
#include <iostream> using namespace std; int n,m; int a[100000]; int b[100000]; int vis[100000]; int c; void dfs(int x,int last) { if(x==n+1) { int all=0; for(int i=1;i<=x;i++)all=all+b[i]; if(all!=m)return ; for(int i=1;i<x-1;i++) { for(int j=i+1;j<x;j++) { if(b[j]<b[i])return ; } } c++; return ; } for(int i=1;i<=m;i++) { b[x]=i; vis[i]=1; dfs(x+1,i); vis[i]=0; b[x]=0; } } int main() { cin>>m>>n; c=0; dfs(1,0); cout<<c<<endl; return 0; }
那么我们就提交吧,神奇,只得了40分其他TLE.
好吧,只能剪枝了.如何剪枝呢反正我不知道
首先让人先想到的是
下一个数必定要大于这个数，也就是说a[x+1]>a[x],所以for可以从a[x]一直到n这就是第一个剪枝，好吧那我们把代码写下来吧:
// luogu-judger-enable-o2 // luogu-judger-enable-o2 // luogu-judger-enable-o2 #include <iostream> using namespace std; int n,m; int a[100000]; int b[100000]; int vis[100000]; int c; void dfs(int x,int last) { if(x==n+1) { int all=0; for(int i=1;i<=x;i++)all=all+b[i]; if(all!=m)return ; for(int i=1;i<x-1;i++) { for(int j=i+1;j<x;j++) { if(b[j]<b[i])return ; } } c++; return ; } for(int i=b[x-1];i<=m;i++) { b[x]=i; vis[i]=1; dfs(x+1,i); vis[i]=0; b[x]=0; } } int main() { cin>>m>>n; c=0; b[0]=1; dfs(1,0); cout<<c<<endl; return 0; }
提交~多对了一个点，那好吧我们还得继续改进
好吧。我们得继续剪枝,我们做一个统计就是all,all要最后算,我们是不是可以先算呢.也就是说
在x==n+1的时候我们只用判断all是不是等于m,就少了一个for
第二我们在后面增加all,加判断all>m?如果大于了肯定就不是了,下面就上AC代码
#include <iostream> using namespace std; int n,m; int b[100000]; int vis[100000]; int c; int all=0; void dfs(int x,int last) { if(x==n+1) { if(all!=m)return ; c++; return ; } for(int i=b[x-1];i+all<=m;i++) { b[x]=i; vis[i]=1; all=all+i; if(all>m)return ; dfs(x+1,i); vis[i]=0; all=all-i; b[x]=0; } } int main() { cin>>m>>n; c=0; b[0]=1; dfs(1,0); cout<<c<<endl; return 0; }
bula bula bula ac 100
-The end-
-by sffy
原文：https://www.cnblogs.com/sffy/p/9677734.html