Blog·Tanky WooABOUTRSS

HDOJ 2200 Eddy's AC难题

02 Sep 2010
这篇博客是从旧博客 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;
}