题解 | #[NOIP2001]数的划分#

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll f[210][10];
int main(){
    int n,k;
    cin>>n>>k;
    f[1][1]=1;
    for(int i=2;i<=n;i++){
        f[i][i]=1;
        f[i][1]=1;
        for(int j=2;j<i&&j<=k;j++){
            f[i][j]=f[i-j][j]+f[i-1][j-1];
        }
    }
    cout<<f[n][k];
    return 0;
}

这题比较简单

给你一堆数，让你划分成k组

无非就只要两种情况，某个排序存在1和某个排列不存在1

如果某个排序存在1，则有f[i-j][j]方案数递推过来

否则由f[i-1][j-1]方案数递推过来

很明显两个子状态互斥

所以直接分两层枚举递推即可