这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目地址: http://acm.hdu.edu.cn/showproblem.php?pid=2200
这道题可以看做从n个中选出2、3...n个人,然后选2个人有1种分发,3个人有2种分发...n个人有n-1种分法 注:这里说的3个人有2种分发只是1|23和12|3两种,以此类推. 那么任意选出两个人有C(n,2)种,选3个人有C(n,3)种...; 那么n个人的答案就是C(n,2)*1+C(n,3)*2+...C(n,n)*(n-1); |
#include
using namespace std;
//f[n][m]代表从n个人中找出m个,即数学中的C(n,m);
__int64 f[100][100],n,m=0;
__int64 work(int n,int m)
{
if (f[n][m])
return f[n][m];
if (n==m||m==0)
return 1;
return f[n][m]=work(n-1,m)+work(n-1,m-1);//n人中任意选m个可能是第n个人没被选中和被选中,没选中就是n-1个人里选m个,选中了就是n-1个人里选m-1个
}
int main()
{
while(scanf("%d", &n;) != EOF)
{
m = 0;
for (int i=2;i<=n;i++)
m += work(n,i)*(i-1);
printf("%I64d\n", m);
}
return 0;
}