2014
11-30

# I, zombie

The "endless" model in "I, zombie" of "Plants vs. Zombies" is my favourite.
The aim of the game is to put down the zombies most reasonable in the right-most , to eat the brain protected by Plants in the left-most.

To simplify the problem ,we provide only one kind of Zombies : normal Zombies with 50 hp each.
The map contains one row only, and we provide two kinds of plants : Peashooter (with 10hp) and Potato Mine.
The operating steps of every second are as below(Warning: make sure your program strictly follow the order of these steps):

1.Put some or none zombies in the right-most grid one by one. (In the right grid of the right-most plant at beginning).
2.Judge every survived zombie, whether he’s standing on a grid with a Peashooter.
2.1.If it’s true, he attacks the Peashooter in his grid, and the Peashooter decreases 1 hp. The Peashooter’s hp may be negative at that moment, but it’s still alive!
2.2.If it’s false, he moves left for one grid.
3.If there are still some zombies in the map, every survived Peashooter will shoot a pea to the zombie who was put earliest. (the zombie’s hp decreases 1 hp for each pea, the zombie’s hp can be negative at that moment, but it’s still alive!)
4.If there are zombies in the grids where Potato Mine stands , then the Potato Mine explodes , all the zombies’ hp in this grid become 0.
5.The plants and zombies with non-positive hp disappear(until now they are dead).

Now, given the map, you are to tell me how many zombies are needed at least, in order to eat the brain in the left-most?

The first line is a number T (1<=T<=100), represents the number of cases.
The next T line with n(0<n<=100) characters ,represents each case ,’P’ represents Peashooters ,’M’ represents Potato Mine ,no other character in the input.

The first line is a number T (1<=T<=100), represents the number of cases.
The next T line with n(0<n<=100) characters ,represents each case ,’P’ represents Peashooters ,’M’ represents Potato Mine ,no other character in the input.

5
PM
PP
PPP
MMMMM
PPMM

Case 1: 2
Case 2: 1
Case 3: 2
Case 4: 6
Case 5: 3

 #include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

const int MAX = 100 + 10;
char Plant[MAX];
int P, M;
int Flag;
int E;
int MozNum;
void init(char plant[])
{
MozNum = 0;
E = strlen(plant) - 1;
P = M = 0;
for(int i = 0; i <= E; ++i)
{
if(plant[i] == 'P')
++P;
else
++M;
}
}

int run(int apNum, int ppNum, int mozNum)
{
int flag = Flag;
int pLife = 10, mozLife = 50;
while(ppNum > 0 && mozNum > 0)
{
if(flag > 0)
{
--flag;
mozLife -= apNum;
}
else
{
pLife -= mozNum;
mozLife -= apNum;
}
if(pLife <= 0)
{
pLife = 10;
apNum--;
ppNum--;
flag = 1;
}
if(mozLife <= 0)
{
mozLife = 50;
mozNum--;
}
}
if(ppNum <= 0 && mozNum > 0)
return 1;
if(ppNum <= 0 && mozNum <= 0)
return 0;
if(ppNum > 0)
return -1;
}
int main()
{
freopen("in.txt", "r", stdin);
int T;
scanf("%d", &T);
for(int t = 1; t <= T; ++t)
{
scanf("%s", Plant);
init(Plant);
if(Plant[E] == 'M')
{
E--;
MozNum++;
Flag = 2;
}
else
Flag = 1;
while(E >= 0)
{
if(Plant[E] == 'M')
{
if(Flag > 1)
{
--Flag;
if(P >= 50)
++MozNum;
continue;
}
else
MozNum++;
M--;
E--;
Flag = 2;
}
else
{
int pNum = 0;
for(int i = E; i >= 0; --i)
{
if(Plant[i] == 'M')
break;
else
pNum++;
}
int left = 1, right = 2 * MAX, mid;
while(left < right)
{
mid = (left + right) >> 1;
if(run(P, pNum, mid) > 0)
right = mid;
else
left = mid + 1;
}
MozNum += left;
P -= pNum;
E -= pNum + 1;
Flag = 2;
}
}
if(Plant[0] == 'M')
++MozNum;
printf("Case %d: %d\n", t, MozNum);
}
return 0;
}


1. 第23行：
hash = -1是否应该改成hash[s ] = -1

因为是要把从字符串s的start位到当前位在hash中重置

修改提交后能accept，但是不修改居然也能accept