[Project Euler 76]Counting summations

题目链接

https://projecteuler.net/problem=76

大意

将100拆分成至少两个数字的可行方案数是多少?

题解

如果做过放苹果这道题目的话,想必做这道题目是比较轻松的。

我们令\(f[i][j]\)表示将\(i\)拆分成\(j\)份的方案数。

那么我们就可以得到这个递推方程:

\(f[i][j]=f[i-1][j-1]+f[i-j][j]\)

边界条件是\(f[i][1]=1,f[i][i]=1\)。

#include <iostream>
#include <cstring>
#include <cmath>
#define MAXN 100
using namespace std;
int f[105][105],ans;
int main()
{
 for(int i=0;i<=MAXN;i++)
  f[i][1]=1,f[i][i]=1;
 for(int i=2;i<=MAXN;i++)
  for(int j=1;j<=i;j++)
   f[i][j]=f[i-1][j-1]+f[i-j][j];
 for(int i=2;i<=MAXN;i++)//应该至少被拆分成两个数
  ans+=f[MAXN][i];
 cout<<ans;
 return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注