P1025 数的划分

此题我是做过的，挑战上的一道题

刚开始想：不就是隔板法吗？但是此题不同顺序算同一种方案，隔板法显然无法解决此类问题，只能用计数类DP

但是由于数据水，暴搜也可以过

我们根据是否包含1划分 ，f[i][j]=f[i-1][j-1]+f[i-j][j];

这体现了“围绕一个基准点把一个大问题划分为两个没有交集的部分”的思想

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

#define go(i,a,b) for(int i=a;i<=b;++i)
#define com(i,a,b) for(int i=a;i>=b;--i)
typedef long long ll;

ll f[206][26];
int n,m;

int main(){
    //freopen("input.txt","r",stdin);
    cin>>n>>m;
    if(m>n){
        puts("0");
        return 0;
    }
    f[0][0]=1;
    go(i,1,n)
        go(j,1,min(i,m)){
            f[i][j]=f[i-1][j-1]+f[i-j][j];
        }
    printf("%lld",f[n][m]);
    return 0;
}

P1025 数的划分

原文：https://www.cnblogs.com/White-star/p/11494306.html