[NOIP2001]数的划分

[编程题][NOIP2001]数的划分

热度指数：1308 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

将整数n分成k份，且每份不能为空，任意两个方案不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种分法被认为是相同的。

1，1，5;

1，5，1;

5，1，1;

问有多少种不同的分法。
输入：n，k ( 6 < n ≤ 200，2 ≤ k ≤ 6 )
输出：一个整数，即不同的分法。

输入描述:

两个整数 n,k ( 6 < n ≤ 200， 2 ≤ k ≤ 6 )

输出描述:

1个整数，即不同的分法。

示例1

输入

7 3

输出

算法知识视频讲解

C/C++

梦樱羽

法一：记忆化搜索

方法为减而治之，把n划分成k份的答案就相当于每次把n分成a，b两个数，再把a分成k-1份，然后把每次a分成k-1份的答案相加即可。注意点是每轮分出来的b要不大于上一轮分出来的b。

#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define rFor(i,t,s) for (int i = (t); i >= (s); --i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
#define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i)

#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl

#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())

#define ms0(a) memset(a,0,sizeof(a))
#define msI(a) memset(a,inf,sizeof(a))

#define pii pair<int,int> 
#define piii pair<pair<int,int>,int> 
#define mp make_pair
#define pb push_back
#define fi first
#define se second

inline int gc(){
    static const int BUF = 1e7;
    static char buf[BUF], *bg = buf + BUF, *ed = bg;
    
    if(bg == ed) fread(bg = buf, 1, BUF, stdin);
    return *bg++;
} 

inline int ri(){
    int x = 0, f = 1, c = gc();
    for(; c<48||c>57; f = c=='-'?-1:f, c=gc());
    for(; c>47&&c<58; x = x*10 + c - 48, c=gc());
    return x*f;
}

typedef long long LL;
const int maxN = 1e5 + 7;

int n, k; 
// f[i][j][k]表示数i分成j分的分法总数，k为限制条件，每种分法每份的值不能超过k，用来排除重复
// f[i][j][k] = f[i-1][j-1][1] + f[i-2][j-1][2] + ……+ f[i-min(k, i-1)][j-1][min(k, i-1)]
int f[201][7][202];

int solve(int x, int y, int z){
    int ret = 0;
    if(x < y) return 0;
    if(y == 1) return x <= z ? 1 : 0;
    if(f[x][y][z]) return f[x][y][z];
    
    For(i, 1, x-1) {
        if(x-i > z) continue;
        ret += solve(i, y-1, x-i);
    }
    f[x][y][z] = ret;
    return ret;
}

int main(){
    scanf("%d%d", &n, &k);
    printf("%d\n", solve(n, k, 201));
    return 0;
}

法二：DP

见代码内注释

#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define rFor(i,t,s) for (int i = (t); i >= (s); --i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
#define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i)

#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl

#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())

#define ms0(a) memset(a,0,sizeof(a))
#define msI(a) memset(a,inf,sizeof(a))

#define pii pair<int,int> 
#define piii pair<pair<int,int>,int> 
#define mp make_pair
#define pb push_back
#define fi first
#define se second

inline int gc(){
    static const int BUF = 1e7;
    static char buf[BUF], *bg = buf + BUF, *ed = bg;
    
    if(bg == ed) fread(bg = buf, 1, BUF, stdin);
    return *bg++;
} 

inline int ri(){
    int x = 0, f = 1, c = gc();
    for(; c<48||c>57; f = c=='-'?-1:f, c=gc());
    for(; c>47&&c<58; x = x*10 + c - 48, c=gc());
    return x*f;
}

typedef long long LL;
const int maxN = 1e5 + 7;

int n, k; 
// f[i][j]表示数i分成j份的分法总数
/*
    当i < j时，很明显没法分，所以f[i][j] = 0；
    当i == j时，只有一种分法，所以f[i][j] = 1；
    当i > j时，考虑从小到大分，第1个如果分1，那么f[i][j] = f[i-1][j-1]；
  第1个如果分大于1的数，可以对所有j份都减一，然后再分，即 f[i][j] = f[i-j][j]； 
  根据加法原则，f[i][j] = f[i-1][j-1] + f[i-j][j]；
*/
int f[201][7]; 

int main(){
    scanf("%d%d", &n, &k);
    For(i, 1, n) f[i][1] = 1; // 无论什么数，分成一份都只有一种 
    For(i, 2, k)
        For(j, 2, n)
            if(j >= i) f[j][i] = f[j-1][i-1] + f[j-i][i];
     
    printf("%d\n", f[n][k]);
    return 0;
}

编辑于 2019-04-08 09:50:28 回复(0)