Submission #1353489

---

Source Code Expand

s = "#" + raw_input()

n = len(s)
DP = [[-n for _ in range(n)] for _ in range(n)]

DP[0][0] = 0
for i, c in enumerate(s):
    m = (i+1) / 2
    for k in range(m+1):
        if c == "g":
            DP[i][k] = max(DP[i-1][k], DP[i-1][k-1] + 1)
        if c == "p":
            DP[i][k] = max(DP[i-1][k] - 1, DP[i-1][k-1])
print max(DP[-1])

Submission Info

Judge Result