7219:复杂的整数划分问题
- 总时间限制:
- 200ms
- 内存限制:
- 65536kB
- 描述
-
将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。
正整数n 的这种表示称为正整数n 的划分。 - 输入
- 标准的输入包含若干组测试数据。每组测试数据是一行输入数据,包括两个整数N 和 K。
(0 < N <= 50, 0 < K <= N) - 输出
- 对于每组测试数据，输出以下三行数据:
第一行: N划分成K个正整数之和的划分数目
第二行: N划分成若干个不同正整数之和的划分数目
第三行: N划分成若干个奇正整数之和的划分数目 - 样例输入
-
5 2
- 样例输出
-
2
3
3 - 提示
- 第一行: 4+1, 3+2,
第二行: 5，4+1，3+2
第三行: 5，1+1+3， 1+1+1+1+1+1 - 题解
- 1.
- f（i,j）表示数字i划分成j部分有几种方案数
- f（i,j）=f（i-1,j-1） 这是划分出来的j部分中一定包含1
- if （i-j>=j） f(i,j)+=f(i-j,j) 划分出来的j部分中都大于1
- 初始值 f（i,1）=f（i,i）=1
- 2.
- 初始值 f（i,1）=1;
- 考虑f(i,j),i需满足i>=j*(j+1)/2 (i最小等于1+2+3+......+j)
- 设划分的j个整数中最小的正整数是k，则从每一部分整数中抽掉1个k，k需满足k*j+j*（j-1)/2<=i
- 对应的方案数 f（i-j*k,j-1） j-1是因为最小数是x，减去x后值为0，因此剩余的数划分成j-1份
- f（i，j）Σf（i-j*k,j-1）
- 3.
- f(i,j)表示数i划分成j个正奇数的方案数
- 初始值
- 对于奇数 f（i，1）=1，f（i,2）=0;
- 对于偶数 f（i,1）=0,f(i,2)=(i/2+1)/2;
- 考虑f（i，j），需满足i>=j
- j>2时
- 若最小的正奇数是1，对应的方案数是 f（i-1，j-1）
- 若最小的正奇数>1,从每个正整数中抽调2，对应的方案数是f（i-2*j,j)
- f(i,j)=f(i-1,j-1)+f(i-2*j,）
-
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int n,k,ans;
int f[55][55];
void xx()
{
ans=0;
memset(f,0,sizeof(f));
}
int main()
{
while (scanf("%d%d",&n,&k)==2)//读入几个数，就等于几
{
//第一问
xx();
for (int i=0;i<=n;i++)
{
f[i][1]=1;
f[i][i]=1;
}
for (int i=2;i<=n;i++)
for (int j=2;j<=k;j++)
{
f[i][j]=f[i-1][j-1];
if (i-j>=j)
f[i][j]+=f[i-j][j];
}
cout<<f[n][k]<<endl;
//第二问
xx();
for (int i=1;i<=n;i++)
f[i][1]=1;
for (int j=2;j*(j+1)/2<=n;j++)
for (int i=j*(j+1)/2;i<=n;i++)
for (int k=1;k*j+j*(j-1)/2<=i;k++)
f[i][j]+=f[i-j*k][j-1];
for (int j=1;j*(j+1)/2<=n;j++)
ans+=f[n][j];
cout<<ans<<endl;
//第三问
xx();
for (int i=1;i<=n;i++)
if (i%2)
{
f[i][1]=1;
f[i][2]=0;
}
else
{
f[i][1]=0;
f[i][2]=(i/2+1)/2;
}
for (int i=3;i<=n;i++)
for (int j=1;j<=i;j++)
{
f[i][j]=f[i-1][j-1];
if (i-2*j>=j)
f[i][j]+=f[i-2*j][j];
}
for (int i=1;i<=n;i++)
ans+=f[n][i];
cout<<ans<<endl;
}
}