这题搜索直接过, 加一个比较简单的剪枝即可, 因为你要把它们想成有序的, 情况才不会多, 所以每个数都应小于等于 还没有搜过的和 / 还剩几个数 即求剩下数的平均值
还可以用 dp 做, 但是没有试过
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- inline int read()
- {
- int f=1,ans=0;char c;
- while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
- while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
- return f*ans;
- }
- int n,k,a[8]={1},t;
- void dfs(int sum,int ans)
- {
- // cout<<sum<<" "<<ans<<endl;
- // system("pause");
- if(sum>n) return;
- if(sum==n&&ans==k+1)
- {
- t++;
- return;
- }
- if(ans>=k+1) return;
- for(int i=a[ans-1];i<=(double)((n-sum)*1.0/(k-ans+1)*1.0);i++)
- {
- a[ans]=i;
- dfs(sum+i,ans+1);
- }
- }
- int main()
- {
- n=read(),k=read();
- dfs(0,1);
- cout<<t;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2693426.html