Time Limit:2000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u
Description
As you know, Hogwarts has four houses: Gryffindor, Hufflepuff, Ravenclaw and Slytherin. The sorting of the first-years into houses is done by the Sorting Hat. The pupils are called one by one in the alphabetical order, each of them should put a hat on his
head and, after some thought, the hat solemnly announces the name of the house the student should enter.
At that the Hat is believed to base its considerations on the student's personal qualities: it sends the brave and noble ones to Gryffindor, the smart and shrewd ones — to Ravenclaw, the persistent and honest ones — to Hufflepuff and the clever and cunning
ones — to Slytherin. However, a first year student Hermione Granger got very concerned about the forthcoming sorting. She studied all the literature on the Sorting Hat and came to the conclusion that it is much simpler than that. If the relatives of the student
have already studied at Hogwarts, the hat puts the student to the same house, where his family used to study. In controversial situations, when the relatives studied in different houses or when they were all Muggles like Hermione's parents, then the Hat sorts
the student to the house, to which the least number of first years has been sent at that moment. If there are several such houses, the choice is given to the student himself. Then the student can choose any of the houses, to which the least number of first
years has been sent so far.
Hermione has already asked the students that are on the list before her about their relatives. Now she and her new friends Harry Potter and Ron Weasley want to find out into what house the Hat will put Hermione.
Input
The first input line contains an integer n (1 ≤ n ≤ 10000). It is the number of students who are in the list before Hermione. The
next line contains n symbols. If all the relatives of a student used to study in the same house, then the i-th character in the string
coincides with the first letter of the name of this house. Otherwise, the i-th symbol is equal to "?".
Output
Print all the possible houses where Hermione can be sent. The names of the houses should be printed in the alphabetical order, one per line.
Sample Input
11 G????SS???H
Gryffindor Ravenclaw
2 H?
Gryffindor Ravenclaw Slytherin
Hint
Consider the second example. There are only two students before Hermione. The first student is sent to Hufflepuff. The second disciple is given the choice between the houses where the least number of students has been sent, i.e. Gryffindor, Slytherin and
Ravenclaw. If he chooses Gryffindor, Hermione is forced to choose between Ravenclaw and Slytherin, if he chooses Ravenclaw, Hermione will choose between Gryffindor and Slytherin, if he chooses Slytherin, Hermione will choose between Gryffindor and Ravenclaw.
In the end, the following situation is possible (it depends on the choice of the second student and Hermione). Hermione will end up 1) in Gryffindor, 2) in Ravenclaw, 3) in Slytherin. Note that, despite the fact that in neither case Hermione will be given
a choice between all the three options, they are all possible and they should all be printed in the answer. Hermione will not, under any circumstances, end up in Hufflepuff.
思路：这题算是DP的题，只是状态转移用递归实现，然后用set单哈希函数判重，减枝，确实挺巧妙的。
dp[a][b][c][d]分别代表四个房子里已经住的人，那么状态转移就是如果？则四个中最小元素相同的都可住，否则直接转移。
用递归就需要减枝，如果dp[a][b][c][d]已经计算过了，那么就不必重复计算，这里用set来当哈希判重。
其实，个人觉得用队列也可以，判重不一定非要用set，用string也行，
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
string name[]={"Gryffindor", "Hufflepuff", "Ravenclaw", "Slytherin"};
typedef vector<int > vc;
vc dp(4,0);///dp状态
bool yes[4];
int n;
set<vc >has;///哈希判重
string get="GHRS?",s;
void dfs(int x)
{
if(has.count(dp))return;///哈希判重减枝
has.insert(dp);
int _min=*min_element(dp.begin(),dp.end());///找最小元素
if(x==n)///全部结束，记录答案
{
for(int i=0;i<4;++i)
if(_min==dp[i])
yes[i]=1;
}
int id=get.find(s[x]);
/**状态转移*/
if(id^4)
{
++dp[id];dfs(x+1);--dp[id];
}
else
{
for(int i=0;i<4;++i)
if(_min==dp[i])
++dp[i],dfs(x+1),--dp[i];
}
}
int main()
{
while(cin>>n>>s)
{ memset(yes,0,sizeof(yes));
has.clear();
dfs(0);
for(int i=0;i<4;++i)
if(yes[i])
cout<<name[i]<<"\n";
}
}