luogu P1025 數的劃分

code

analysis

解題思路來自某谷大佬如下：

t放在最外面就可以避免重複，其原因在于這種解法就相當于将t看作已經切好的一段不變

code

#include<bits/stdc++.h>
using namespace std;
#define loop(i,start,end) for(register int i=start;i<=end;++i)
#define clean(arry,num) memset(arry,num,sizeof(arry))
int n,k;
const int maxn=200+5,maxk=10;
int f[maxn][maxk];
int main()
{
    scanf("%d%d",&n,&k);
    clean(f,0);
    f[0][0]=1;
    loop(t,1,n)
        loop(i,t,n)
            loop(j,1,k)
                f[i][j]+=f[i-t][j-1];
    printf("%d\n",f[n][k]);
    return 0;
}