暴力dfs，怎么看都是要超时的居然还能过系统测试。。。。。
看来TC的电脑比我的好太多了。。。。
Problem Statement |
|||||||||||||
| Elly and Kris play the following game. In the beginning there are several boxes aligned in a row. The boxes may or may not contain candy. As a matter of fact, the girls know exactly how many candies each of them contains. This information is given to you
in the vector <int> sweets. Starting with Elly, the girls make moves in alternating order. A single move looks as follows: the player whose turn it is chooses one of the non-empty boxes and takes all the sweets from it. After that the amount of candy in the neighboring boxes is doubled. For example, suppose that there were five boxes with {20, 50, 70, 0, 30} sweets, respectively. If the girl whose turn it was chose box 0, then in the next turn the number of sweets in the boxes would be {0, 100, 70, 0, 30}. If she chose box 1, then it would be {40, 0, 140, 0, 30}. If she chose box 2, it would be {20, 100, 0, 0, 30}. If she chose box 4, it would be {20, 50, 70, 0, 0}. Note that the girl cannot choose box 3, because it is empty. The game ends when all boxes are empty. The winner of the game is the girl who has more candies at the end of the game. Return the name of the girl that will win the game if both girls play optimally, or "Draw" if they end up with the same number of candies. |
|||||||||||||
Definition |
|||||||||||||
|
|||||||||||||
Limits |
|||||||||||||
|
|||||||||||||
Notes |
|||||||||||||
| - | Playing optimally means that if there is a move, which guarantees that the girl whose turn it is will win no matter what the other girl does, she will play it. If there is no such move, but there is one, which would guarantee a draw, she will use it instead. | ||||||||||||
| - | The game always ends after a finite number of moves, because the number of empty boxes increases in each step. | ||||||||||||
Constraints |
|||||||||||||
| - | sweets will contain between 1 and 10 elements, inclusive. | ||||||||||||
| - | Each element of sweets will be between 0 and 1000, inclusive. | ||||||||||||
Examples |
|||||||||||||
| 0) | |||||||||||||
|
|||||||||||||
| 1) | |||||||||||||
|
|||||||||||||
| 2) | |||||||||||||
|
|||||||||||||
| 3) | |||||||||||||
|
|||||||||||||
| 4) | |||||||||||||
|
|||||||||||||
| 5) | |||||||||||||
|
|||||||||||||
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
class EllysCandyGame {
public:
int dfs(vector<int> sweets,int m)
{
if(m==0) return 0;
int ans=-INF;
for(int i=0;i<sweets.size();i++)
{
if(sweets[i]==0) continue;
vector<int> temp=sweets;
int v=temp[i];
temp[i]=0;
if(i-1>=0) temp[i-1]*=2;
if(i+1<sweets.size()) temp[i+1]*=2;
v-=dfs(temp,m-1);
ans=max(ans,v);
}
return ans;
}
string getWinner(vector <int> sweets)
{
int m=0;
for(int i=0;i<sweets.size();i++)
if(sweets[i]) m++;
int diff=dfs(sweets,m);
if(diff>0) return "Elly";
else if(diff<0) return "Kris";
else return "Draw";
}
};
SRM 606 DIV2 1000 EllysCandyGame
原文：http://blog.csdn.net/u012797220/article/details/18883195