Vijos 数的划分 题解

描述

将整数n分成k份,且每份不能为空,任意两份不能相同(不考虑顺序)。

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

1,1,5; 1,5,1; 5,1,1;
问有多少种不同的分法。

格式

输入格式

输入n,k (6<n<=200,2<=k<=6)

输出格式

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

样例1

样例输入1

1
7 3

样例输出1

1
4

限制

每个测试点1s

来源

NOIP2001第二题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<cstring>
using namespace std;
int DP[201][201][8];
int n,k;
int dp(int n_max,int remain,int num){
    if(remain==0&&num==0)return 1;
    if(remain!=0&&num==0||n_max>remain)return 0;
    if(DP[n_max][remain][num]!=-1)return DP[n_max][remain][num];
    return DP[n_max][remain][num]=dp(n_max,remain-n_max,num-1)+dp(n_max+1,remain,num);
}
int main(){
    memset(DP,-1,sizeof(DP));
    cin>>n>>k;
    cout<<dp(1,n,k);
}

20180730:洛谷P1025重做:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<algorithm>
using namespace std;

int dfs(int n, int k, int nmin) {
    if (k == 0)return n == 0;
    int sum = 0;
    for (int i = nmin; i <= n; i++) {
        if (n - nmin < 0)break;
        sum += dfs(n - i, k - 1, i);
    }
    return sum;
}
int main() {
    int n, k;
    cin >> n >> k;
    cout << dfs(n, k, 1);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注