自动搬运

查看原文

来自洛谷，原作者为

	s_r_f 这里是一个只会背板和fst的蒟蒻

搬运于2025-08-24 21:20:03，当前版本为作者最后更新于2017-08-25 21:13:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题我们可以用dp:

f[i][x] 表示 i 分成 x 个非空的数的方案数。

显然 i<x 时 f[i][x]=0 , i=x 时 f[i][x]=1;

其余的状态，我们分情况讨论：

①有1的 ②没有1的

第一种情况，方案数为 f[i-1][x-1]

第二种情况，方案数为 f[i-x][x] (此时 i 必须大于 x)

所以，状态转移方程为： f[i][x]=f[i-1][x-1]+f[i-x][x]

程序如下：

#include<bits/stdc++.h>
using namespace std;
int n,k,f[201][7];  //f[k][x] k 分成 x 份 ={f[k-1][x-1],f[k-x][x]}
int main(){
    cin >> n >> k;
    for (int i=1;i<=n;i++) {f[i][1]=1;f[i][0]=1;}for (int x=2;x<=k;x++) {f[1][x]=0;f[0][x]=0;}  // 边界，为了防止炸，我把有0的也处理了
    for (int i=2;i<=n;i++)
        for (int x=2;x<=k;x++)
            if (i>x) f[i][x]=f[i-1][x-1]+f[i-x][x];
            else f[i][x]=f[i-1][x-1];
    cout<<f[n][k];
    return 0;
}