HDOJ 2200 Eddy’s AC难题

题目地址:
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);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
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;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDOJ 2200 Eddy’s AC难题》有1个想法

发表评论

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