首页 > ACM题库 > HDU-杭电 > hdu 2412 Party at Hali-Bula-字符串-[解题报告]C++
2014
01-26

hdu 2412 Party at Hali-Bula-字符串-[解题报告]C++

Party at Hali-Bula

问题描述 :

Dear Contestant,

I’m going to have a party at my villa at Hali-Bula to celebrate my retirement from BCM. I wish I could invite all my co-workers, but imagine how an employee can enjoy a party when he finds his boss among the guests! So, I decide not to invite both an employee and his/her boss. The organizational hierarchy at BCM is such that nobody has more than one boss, and there is one and only one employee with no boss at all (the Big Boss)! Can I ask you to please write a program to determine the maximum number of guests so that no employee is invited when his/her boss is invited too? I’ve attached the list of employees and the organizational hierarchy of BCM.

Best,
–Brian Bennett

P.S. I would be very grateful if your program can indicate whether the list of people is uniquely determined if I choose to invite the maximum number of guests with that condition.

输入:

The input consists of multiple test cases. Each test case is started with a line containing an integer n (1 ≤ n ≤ 200), the number of BCM employees. The next line contains the name of the Big Boss only. Each of the following n-1 lines contains the name of an employee together with the name of his/her boss. All names are strings of at least one and at most 100 letters and are separated by blanks. The last line of each test case contains a single 0.

输出:

The input consists of multiple test cases. Each test case is started with a line containing an integer n (1 ≤ n ≤ 200), the number of BCM employees. The next line contains the name of the Big Boss only. Each of the following n-1 lines contains the name of an employee together with the name of his/her boss. All names are strings of at least one and at most 100 letters and are separated by blanks. The last line of each test case contains a single 0.

样例输入:

6
Jason
Jack Jason
Joe Jack
Jill Jason
John Jack
Jim Jill
2
Ming
Cho Ming
0

样例输出:

4 Yes
1 No


题目描述

Dear Contestant,

I’m going to have a party at my villa at Hali-Bula to celebrate my retirement from BCM. I wish I could invite all my co-workers, but imagine how an employee can enjoy a party when he finds his boss among the guests! So, I decide not to invite both an employee and his/her boss. The organizational hierarchy at BCM is such that nobody has more than one boss, and there is one and only one employee with no boss at all (the Big Boss)! Can I ask you to please write a program to determine the maximum number of guests so that no employee is invited when his/her boss is invited too? I’ve attached the list of employees and the organizational hierarchy of BCM.

Best,
–Brian Bennett

P.S. I would be very grateful if your program can indicate whether the list of people is uniquely determined if I choose to invite the maximum number of guests with that condition.

输入格式

The input consists of multiple test cases. Each test case is started with a line containing an integer n (1 ≤ n ≤ 200), the number of BCM employees. The next line contains the name of the Big Boss only. Each of the following n-1 lines contains the name of an employee together with the name of his/her boss. All names are strings of at least one and at most 100 letters and are separated by blanks. The last line of each test case contains a single 0.

输出格式

For each test case, write a single line containing a number indicating the maximum number of guests that can be invited according to the required condition, and a word Yes or No, depending on whether the list of guests is unique in that case.

样例输入

6

Jason

Jack Jason

Joe Jack

Jill Jason

John Jack

Jim Jill

2

Ming

Cho Ming

0

样例输出

4 Yes

1 No

题目分析

非常明显,此题是一道树形DP题。

首先,需要将人名转化成对应编号,这里需要注意,某一行第一个人的BOSS不一定是先前出现过的,所以,两个人名都需要判断一次是否出现过。(C++建议使用string库,否则字符串处理会冗杂很多)。cn[i]为统计的每个节点的孩子数,c[i][j]为第i号节点的第j个儿子。最终求的值为maxdata[1][1], data[1][0]

建立树形DP的状态转移方程。data[i][0]i号节点不去,data[i][1]为第i号节点去

data[i][1] = sum(data[k][0]) k = 1 to cn[i]。由于该节点去,所以他的孩子节点必须不去。

data[i][0] = smm(max(data[k][0], data[k][1]))k = 1 to cn[i]。由于该节点不去,所以他的孩子节点去不去都可以。

接下来就是考虑边界条件。

如果该节点已经没有孩子,那么data[i][j] = j

然而,此题难点并不在于求出人数,而是如何判断是否多解。如何判断是否多解呢?经分析得出,只要某一点为多解,且该点是最优解中的一部分,那么结果就是“NO”。所以再开一个bool数组data2来存储多解情况,先把data2全部附成true

如果j = 0 ①、data[c[i][k]][0] < data[c[i][k]][1]并且 data2[c[i][k]][1] false

                   ②、data[c[i][k]][0] > data[c[i][k]][1]并且 data2[c[i][k]][0] false

                      ③、data[c[i][k]][0] = data[c[i][k]][1]

                      这三种情况时,该节点的data2值改变成false

如果j = 1data2[x[i][k]][0]false时,该节点的值才为false

最终,如果data[1][0] > data[1][1] 那么按照data2[1][0]的值输出,反之亦然。

参考程序

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<iostream>

#define maxn 2100

using namespace std;

int n, ll[maxn], cn[maxn], c[maxn][maxn], data[maxn][2];

bool data2[maxn][2];

void dp(int i, int j)

{

       int k, p = 0;

       if(!cn[i])

       {

              j ? data[i][j] = 1 : data[i][j] = 0;//如果该节点是叶子节点,那么如果他去就返回1,不去就返回0

              return;

       }

       for(k = 1; k <= cn[i]; k++)

       {

              if(j == 0)

              {

                     if(!data[c[i][k]][0]) dp(c[i][k], 0);

                     if(!data[c[i][k]][1]) dp(c[i][k], 1);

                     p += max(data[c[i][k]][0], data[c[i][k]][1]);//他不去,所以他的孩子节点去不去都行

                     if(data[c[i][k]][0] < data[c[i][k]][1])

                            if(data2[c[i][k]][1] == false) data2[i][j] = false;

                     if(data[c[i][k]][0] > data[c[i][k]][1])

                            if(data2[c[i][k]][0] == false) data2[i][j] = false;

                     //去的较大值的那种情况如果已经是多解,那么他也是多解

                     if(data[c[i][k]][0] == data[c[i][k]][1]) data2[i][j] = false;//如果他本身已经是多解,那么他就是多解

              }

              if(j == 1)//该节点去

              {

                     if(!data[c[i][k]][0]) dp(c[i][k], 0);

                     p += data[c[i][k]][0]; //他的孩子节点只能不去

                     if(data2[c[i][k]][0] == false) data2[i][j] = false;//如果他的孩子节点已是多解,那么他就是多解

              }

       }

       if(j) ++p;

       data[i][j] = p;

}

 

int main()

{

       int i, l, j, k, used, ans1, ans2;

       string name[maxn], x1, x2;

//     freopen(“party.in”, “r”, stdin);

       while(1)

       {

              used = 1;

              memset(cn, 0, sizeof(cn));

              memset(c, 0, sizeof(c));

              memset(data, 0, sizeof(data));

              memset(data2, true, sizeof(data2));

              cin>>n;  if(!n) break;

              cin>>name[1];

              for(i = 2; i <= n; i++)

              {

                     cin>>x1>>x2;

                     ans1 = ans2 = -1;

                     for(j = 1; j <= used; j++)

                     {

                            if(name[j] == x1) ans1 = j;

                            if(name[j] == x2) ans2 = j;

                     }//找到当前的两个字串所在位置

                     if(ans1 == -1)

                     {

                            ans1 = ++used;

                            name[used] = x1;

                     }//如果第一个字串没有,那么新增一个

                     if(ans2 == -1)

                     {

                            ans2 = ++used;

                            name[used] = x2;

                     }//如果第一个字串没有,新增一个

                     c[ans2][++cn[ans2]] = ans1;//将两个字串转化成树中的数字关系

              }

              dp(1, 0);dp(1, 1);

              printf(“%d “, max(data[1][0], data[1][1]));//输出较大值

              if(data[1][0] == data[1][1]) printf(“No\n”);

              else if(data[1][0] > data[1][1]) {if(data2[1][0] == true) printf(“Yes\n”);else printf(“No\n”);}

              else if(data[1][0] < data[1][1]) {if(data2[1][1] == true) printf(“Yes\n”);else printf(“No\n”);}//以上三种是判断是否多解

       }

       return 0;

}

 

 

 

解题转自:http://tianyong1995.blog.163.com/blog/static/2077223442012539212588/


  1. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环

  2. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1