SDNU 1029.巧分整数

1029.巧分整数

Time Limit: 1000 MS Memory Limit: 32768 KB
Total Submission(s): 174 Accepted Submission(s): 90

Description
聪明的lg给syc出了一道简单的题目,syc把脑细胞都用光了也不知道该怎么去做,那么请厉害的你来帮助syc做做这道题目。题目的要求就是取一个整数n,这个整数n大于0小于等于200,然后把这个整数n分为k份,并且每一份不能为0,而且任意两种分法不能相同(不考虑顺序)。

例如:n=8,k=3, 下面三种分法被认为是相同的。
2,2,4;  4,2,2;  2,4,2;

问有多少种不同的分法。

Input
n,k (k<=n<=200,1<=k<=6)

Output
一个整数,即不同的分法。

Sample Input
8 3

Sample Output
5

题解:
很有意思的一道题,一开始看数据小还想暴力,结果一算复杂度果断放弃,其实是一道典型的dp,说一下dp的思路。
首先定一个数组 dp[][] , dp[i][j] 代表将数字 i 分成 j 份时的分法。
然后观察一下,首先每一份都必须要有一份,就可以先把每一份都放入 1。然后剩下 i-j 个随便放,也就是从只放 1 份里到所有 j 份都放的一个求和。
所以,可以得出最基础的公式 dp[i][j] = dp[i-j][1] + dp[i-j][2] + … + dp[i-j][j]。
有些麻烦,试着化简一下。由推出的公式,可以得到 dp[i-1][j-1] = dp[i-j][1] + dp[i-j][2] + … + dp[i-j][j-1]。
所以,dp[i][j] = dp[i-1][j-1] + dp[i-j][j]。
得出公式之后就很简单了,一层层向下推就行了。

Ac代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll;

int main()
{
int n, k;
int dp[210][10];
memset(dp,0,sizeof dp);
dp[0][0] = 1;
for(int i = 1; i <= 200; i++)
for(int j = 1; j <= 6; j++)
if(i >= j)
dp[i][j] = dp[i-1][j-1] + dp[i-j][j];
while(cin >> n >> k)
{
cout << dp[n][k] << endl;
}
return 0;
}
我好饿呀!求打赏!