首页 > ACM题库 > HDU-杭电 > hdu 1990 Monkey Vines-模拟-[解题报告]C++
2013
12-26

hdu 1990 Monkey Vines-模拟-[解题报告]C++

Monkey Vines

问题描述 :

Deep in the Amazon jungle, exceptionally tall trees grow that support a rich biosphere of figs and juniper bugs, which happen to be the culinary delight of brown monkeys.
Reaching the canopy of these trees requires the monkeys to perform careful navigation through the tall tree’s fragile vine system. These vines operate like a see-saw: an unbalancing of weight at any vine junction would snap the vine from the tree, and the monkeys would plummet to the ground below. The monkeys have figured out that if they work together to keep the vines properly balanced, they can all feast on the figs and juniper bugs in the canopy of the trees.
A vine junction supports exactly two sub-vines, each of which must contain the same number of monkeys, or else the vine will break, leaving a pile of dead monkeys on the jungle ground. For purposes of this problem, a vine junction is denoted by a pair of matching square brackets [ ], which may contain nested information about junctions further down its sub-vines. The nesting of vines will go no further than 25 levels deep.

You will write a program that calculates the minimum number of monkeys required to balance a particular vine configuration. There is always at least one monkey needed, and, multiple monkeys may hang from the same vine.

输入:

The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of datasets that follow.
Each dataset consists of a single line of input containing a vine configuration consisting of a string of [ and ] characters as described above. The length of the string of [ and ] will be greater than or equal to zero, and less than or equal to 150.

输出:

The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of datasets that follow.
Each dataset consists of a single line of input containing a vine configuration consisting of a string of [ and ] characters as described above. The length of the string of [ and ] will be greater than or equal to zero, and less than or equal to 150.

样例输入:

3
[]

[[][[]]]

样例输出:

1 2
2 1
3 8

水题, 如果最大深度为h ( 不含根节点), 则结果为1<<h;


#ifdef _MSC_VER
#define DEBUG
#endif

#include <fstream>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <limits.h>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <functional>
#include <ctype.h>
#include <stack>
using namespace std;

int main(void)
{
#ifdef DEBUG  
  freopen("../stdin.txt","r",stdin);
  freopen("../stdout.txt","w",stdout); 
#endif  

  stack<char> mstack;
  int ncases;
  char str[200];
  scanf("%d",&ncases);
  getchar();

  for(int nc=1;nc<=ncases;++nc)
  {
	  gets(str);
	  int len=strlen(str);
	  while(!mstack.empty())
		  mstack.pop();
	  int total=0,maxlen=0;
	  for(int i=0;i<len;++i)
		  if(str[i]=='[')
		  {
			  mstack.push('[');
        ++total;
			  maxlen=max(total,maxlen);
		  }
		  else
      {
        --total;
			  mstack.pop();
      }
	  printf("%d %d\n",nc,1<<maxlen);
  }

  return 0;
}

解题转自:http://blog.csdn.net/neofung/article/details/7235093


  1. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3