[NOIP2001 提高组] 数的划分
题目描述
将整数 分成 份,且每份不能为空,任意两个方案不相同(不考虑顺序)。
例如:,,下面三种分法被认为是相同的。
;
;
.
问有多少种不同的分法。
输入格式
(,)
输出格式
个整数,即不同的分法。
样例 #1
样例输入 #1
7 3
样例输出 #1
4
提示
四种分法为:
;
;
;
.
【题目来源】
NOIP 2001 提高组第二题
#include <cstdio>
#include <iostream>
using namespace std;
int main()
{
int n,k;
cin >> n >> k;
int ans = 0;
for(int i1 = 1; i1 <= n / 2; i1 ++)
{
for(int i2 = i1; i2 <= n / 2 ;i2 ++)
{
for(int i3 = i2; i3 <= n / 2; i3 ++)
{
for(int i4 = i3; i4 <= n / 2; i4 ++)
{
for(int i5 = i4; i5 <= n / 2; i5 ++)
{
if(k == 2)
{
if(i5 <= n - i5) ans ++;
}
else if(k == 3)
{
if(i4 <= n - i4 - i5 && i5 <= n - i4 - i5) ans ++;
}
else if(k == 4)
{
if(i4 <= n - i4 - i5 - i3 && i5 <= n - i4 - i5 - i3 && i3 <= n - i3 - i4 - i5) ans ++;
}
else if(k == 5)
{
if(i4 <= n - i4 - i5 - i3 - i2 && i5 <= n - i4 - i5 - i3 - i2 && i3 <= n - i3 - i4 - i5 - i2 && i2 <= n - i3 - i4 - i5 - i2) ans ++;
}
else if(k == 6)
{
if(i4 <= n - i4 - i5 - i3 - i2 - i1 && i5 <= n - i4 - i5 - i3 - i2 - i1 && i3 <= n - i3 - i4 - i5 - i2 - i1 && i2 <= n - i3 - i4 - i5 - i2 - i1 && i1 <= n - i3 - i4 - i5 - i2 - i1) ans ++;
}
}
if(k < 3) break;//保证当k<3只能使这层的循环只能运行一次
}
if(k < 4) break;//保证当k<4只能使这层的循环只能运行一次
}
if(k < 5) break;//保证当k<5只能使这层的循环只能运行一次
}
if(k < 6) break;//保证当k<6只能使这层的循环只能运行一次
}
printf("%d\n",ans);
return 0;
}