注(具体请见🎉大家好,我是3月份新人榜排名第三的 ༺Blog༒Hacker༻
💬支持我:点赞👍+收藏⭐️+留言📝
🌺格言:༺永做优质༒programmer༻
CF665B Shopping
):
我的更新时间会有所改变,每月2-4
篇,感谢各位长期以来的支持!
题目描述
任何一个自然数n,总可以拆分成若干个自然数之和。
当n=7共15种拆分方法:
7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4
7=7
total=15
输入格式
一行一个整数n。
输出格式
所有拆分方案,具体格式见【样例】。
样例数据
input
4
output
1+1+1+1
1+1+2
1+3
2+2
4
total=5
数据规模与约定
1≤n≤20
💯code
#include
using namespace std;
int n,a[50],cnt=0,last=0;
void DFS(int deep,int k)
{
if(deep==0)
{
cnt++;
for(int i=1;i<=last-1;++i)
{
cout<<a[i]<<"+";
}
cout<<a[last]<<endl;
return;
}
int p;
p=deep/2;
for(int i=k;i<=p;++i)
{
last++;
a[last]=i;
DFS(deep-i,i);
last--;
}
last++;
a[last]=deep;
DFS(0,deep);
last--;
}
signed main()
{
cin>>n;
DFS(n,1);
cout<<"total="<<cnt<<endl;
return 0;
}
点赞收藏是我更新的动力,下期再见,拜拜!
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)