Problem:


Daruma Otoshi

You are playing a variant of a game called "Daruma Otoshi (Dharma Block Striking)".

At the start of a game, several wooden blocks of the same size but with varying weights
are stacked on top of each other, forming a tower.
Another block symbolizing Dharma is placed atop.
You have a wooden hammer with its head thicker than the height of a block,
but not twice that.

You can choose any two adjacent blocks, except Dharma on the top,
differing at most 1 in their weight,
and push both of them out of the stack with a single blow of your hammer.
The blocks above the removed ones then fall straight down,
without collapsing the tower.

You cannot hit a block pair with weight difference of 2 or more,
for that makes too hard to push out blocks while keeping the balance of the tower.
There is no chance in hitting three blocks out at a time,
for that would require superhuman accuracy.

The goal of the game is to remove as many blocks as you can.
Your task is to decide the number of blocks that can be removed
by repeating the blows in an optimal order.

Figure D1. Striking out two blocks at a time

In the above figure, with a stack of four blocks weighing 1, 2, 3, and
1, in this order from the bottom, you can hit middle
two blocks, weighing 2 and 3, out from the stack.  The blocks above will
then fall down, and two blocks weighing 1 and the Dharma block will remain.
You can then push out the remaining pair of weight-1 blocks after that.

Input

The input consists of multiple datasets.
The number of datasets is at most 50.
Each dataset is in the following format.

n 

w1 w2 &hellip; wn 

n is the number of blocks, except Dharma on the top.
n is a positive integer not exceeding 300.
wi gives the weight of the i-th block counted from the bottom.
wi is an integer between 1 and 1000, inclusive.

The end of the input is indicated by a line containing a zero.

Output

For each dataset, output in a line the maximum number of blocks you can remove.

Sample Input

4
1 2 3 4
4
1 2 3 1
5
5 1 2 3 6
14
8 7 1 4 3 5 4 1 6 8 10 4 6 5
5
1 3 5 1 3
0

Output for the Sample Input

4
4
2
12
0



Sample input:
4
1 2 3 4
4
1 2 3 1
5
5 1 2 3 6
14
8 7 1 4 3 5 4 1 6 8 10 4 6 5
5
1 3 5 1 3
0


Sample output:
4
4
2
12
0

Submission status: Accepted

Solution code:

while True:
    n=int(input())
    if n== 0:
        break
    
    A = list(map(int, input().split()))
    c = [[0]*n for _ in range(n)]
    for i in range(n):
        c[i][i] = 0
        
    for i in range(1, n):
        if i%2==0:
            continue
        for j in range(n-i):
            if i==1 and abs(A[j] - A[j+i])<=1:
                    c[j][j+i] = 1 
            else:
                for k in range(j+1, j+i-1):
                    #print(f'j:{j}, i:{i}, k:{k}, c[j][k]{c[j][k]} and c[k+1][j+i]{c[k+1][j+i]}')
                    if c[j][k] and c[k+1][j+i]:
                        c[j][j+i] = 1
                        break
                if c[j+1][j+i-1] and abs(A[j] - A[j+i])<=1:
                    c[j][j+i] = 1
    
    dp = [[0]*n for _ in range(n)]
    
    for i in range(1):
        for j in range(i, n):
            if c[i][j]:
                dp[i][j] = j-i+1
            else:
                for k in range(i, j):
                    if c[k+1][j]:
                        dp[i][j] = max(dp[i][j], dp[i][k] + j-k)
                if j>i:
                    dp[i][j] = max(dp[i][j], dp[i][j-1])
    
    print(dp[0][n-1])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
import sys
input = lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 8)
def solve():
    n = int(input())
    while n != 0:
        w = tuple(map(int, input().split()))
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                if (j - i + 1) % 2 == 0:
                    if dp[i + 1][j - 1] == j - i - 1 and abs(w[i] - w[j]) <= 1:
                        dp[i][j] = dp[i + 1][j - 1] + 2
                    else:
                        p = tuple(dp[i][k] + dp[k + 1][j] for k in range(i, j + 1))
                        dp[i][j] = max(p)
                else:
                    dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
        print(dp[0][n - 1])
        n = int(input())


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:

def main():
    while True:
        N = int(input())
        if N == 0:
            exit()
        A = list(map(int,input().split()))
        can_drop = [[False] * N for _ in range(N)]
        # d[i]: i個のブロック列で最大何個落とせるか
        d = [0] * (N+1)

        # 隣接するのが落とせるかどうか
        for i in range(N-1):
            if abs(A[i] - A[i+1]) <= 1:
                can_drop[i][i+1] = True

        # 何個分をみるか。一個増えても落とせるやつ個数が増えたりしないので２刻み
        for i in range(3, N, 2):
            # どのブロックはじめで見るか。
            for j in range(N-i):
                # 間
                last = j + i
                for k in range(j+1, j+i):
                    # j~lastまでで落とせないが、j~k, k+1~lastに分けてみると、両方の部分で結果的にj~lastで落とせる場合
                    if not can_drop[j][last] and can_drop[j][k] and can_drop[k+1][last]:
                        can_drop[j][last] = True
                        break
                # j ~ lastで落ちないが、j+1~last-1で落とせて、jとlastの差が１以下の場合は、j~lastで落とせると言える
                if not can_drop[j][last] and can_drop[j+1][last-1] and abs(A[j] - A[last]) <= 1:
                    can_drop[j][last] = True

        # can_dropのTrueが続いている最長部分を探す
        for i in range(N):
            for j in range(N):
                if can_drop[j][i]:
                    d[i] = max(d[i], d[j-1] + i - j + 1)
        
            d[i] = max(d[i], d[i - 1])
        print(d[N-1])        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
while True:
    l1 = list(map(int,input().split()))
    c = [[False] * n for i in range(n)]
    d = [0] * (n + 1)
    for i in range(n - 1):
        if abs(l1[i + 1] - l1[i]) <= 1:
            c[i][i + 1] = True
            
    for i in range(3, n, 2):
        for j in range(n - i):
            for k in range(j + 1, j + i):
                if c[j][j + i] == False and c[j][k] and c[k + 1][j + i]:
                    c[j][j + i] = True
                    break
            if c[j][j + i] == False and abs(l1[j] - l1[j + i]) <= 1 and c[j + 1][j + i - 1]:
                c[j][j + i] = True
                
    for i in range(n):
        for j in range(i):
            if c[j][i]:
                d[i] = max(d[i], d[j - 1] + i - j + 1)
        d[i] = max(d[i], d[i - 1])
        
    print(d[n - 1])
    
    n = int(input())
    if n == 0:
        break

Submission status: Accepted

Solution code:
#2006_D
"""
import sys
from collections import defaultdict
def dfs(d,y,x,f):
    global ans
    if d >= 10:
        return
    f_ = defaultdict(int)
    for i in f.keys():
        f_[i] = f[i]
    for t,s in vr[(y,x)]:
        if a[t][s] == 3:
            ans = min(ans,d+1)
            break
        elif f[(t,s)]:
            if s == x+1:
                break
            f_[(t,s)] = 0
            dfs(d+1,t,s-1,f_)
            f_[(t,s)] = 1
            break

    for t,s in vl[(y,x)]:
        if a[t][s] == 3:
            ans = min(ans,d+1)
            break
        elif f[(t,s)]:
            if s == x-1:
                break
            f_[(t,s)] = 0
            dfs(d+1,t,s+1,f_)
            f_[(t,s)] = 1
            break

    for t,s in vd[(y,x)]:
        if a[t][s] == 3:
            ans = min(ans,d+1)
            break
        elif f[(t,s)]:
            if t == y+1:
                break
            f_[(t,s)] = 0
            dfs(d+1,t-1,s,f_)
            f_[(t,s)] = 1
            break

    for t,s in vu[(y,x)]:
        if a[t][s] == 3:
            ans = min(ans,d+1)
            break
        elif f[(t,s)]:
            if t == y-1:
                break
            f_[(t,s)] = 0
            dfs(d+1,t+1,s,f_)
            f_[(t,s)] = 1
            break
    return
while 1:
    w,h = map(int, sys.stdin.readline()[:-1].split())
    if w == h == 0:
        break
    a = [list(map(int, sys.stdin.readline()[:-1].split())) for i in range(h)]
    vr = defaultdict(list)
    vl = defaultdict(list)
    vd = defaultdict(list)
    vu = defaultdict(list)
    f = defaultdict(int)
    for y in range(h):
        for x in range(w):
            if a[y][x] == 1:
                f[(y,x)] = 1
            if a[y][x] in [1,3]:
                for x_ in range(x):
                    vr[(y,x_)].append((y,x))
            elif a[y][x] == 2:
                sy,sx = y,x
    for y in range(h):
        for x in range(w)[::-1]:
            if a[y][x] in (1,3):
                for x_ in range(x+1,w):
                    vl[(y,x_)].append((y,x))
    for x in range(w):
        for y in range(h):
            if a[y][x] in (1,3):
                for y_ in range(y):
                    vd[(y_,x)].append((y,x))
    for x in range(w):
        for y in range(h)[::-1]:
            if a[y][x] in (1,3):
                for y_ in range(y+1,h):
                    vu[(y_,x)].append((y,x))
    ind = [[[0]*4 for i in range(w)] for j in range(h)]
    ans = 11
    dfs(0,sy,sx,f)
    ans = ans if ans < 11 else -1
    print(ans)
"""

#2018_D
"""
import sys
from collections import defaultdict
sys.setrecursionlimit(1000000)

def dfs(d,s,l,v,dic):
    s_ = tuple(s)
    if dic[(d,s_)] != None:
        return dic[(d,s_)]
    if d == l:
        dic[(d,s_)] = 1
        for x in s:
            if x > (n>>1):
                dic[(d,s_)] = 0
                return 0
        return 1
    else:
        res = 0
        i,j = v[d]
        if s[i] < (n>>1):
            s[i] += 1
            res += dfs(d+1,s,l,v,dic)
            s[i] -= 1
        if s[j] < (n>>1):
            s[j] += 1
            res += dfs(d+1,s,l,v,dic)
            s[j] -= 1
        dic[(d,s_)] = res
        return res

def solve(n):
    dic = defaultdict(lambda : None)
    m = int(sys.stdin.readline())
    s = [0]*n
    f = [[1]*n for i in range(n)]
    for i in range(n):
        f[i][i] = 0
    for i in range(m):
        x,y = [int(x) for x in sys.stdin.readline().split()]
        x -= 1
        y -= 1
        s[x] += 1
        f[x][y] = 0
        f[y][x] = 0
    v = []
    for i in range(n):
        for j in range(i+1,n):
            if f[i][j]:
                v.append((i,j))
    l = len(v)
    print(dfs(0,s,l,v,dic))

while 1:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    solve(n)
"""
#2011_D
"""
import sys
def dfs(s,d,f,v):
    global ans
    if ans == n-n%2:
        return
    if d > ans:
        ans = d
    for i in range(n):
        if s[i] == 0:
            for j in range(i+1,n):
                if s[j] == 0:
                    if f[i] == f[j]:
                        s[i] = -1
                        s[j] = -1
                        for k in v[i]:
                            s[k] -= 1
                        for k in v[j]:
                            s[k] -= 1
                        dfs(s,d+2,f,v)
                        s[i] = 0
                        s[j] = 0
                        for k in v[i]:
                            s[k] += 1
                        for k in v[j]:
                            s[k] += 1

def solve(n):
    p = [[int(x) for x in sys.stdin.readline().split()] for i in range(n)]
    v = [[] for i in range(n)]
    f = [0]*n
    s = [0]*n
    for i in range(n):
        x,y,r,f[i] = p[i]
        for j in range(i+1,n):
            xj,yj,rj,c = p[j]
            if (x-xj)**2+(y-yj)**2 < (r+rj)**2:
                v[i].append(j)
                s[j] += 1
    dfs(s,0,f,v)
    print(ans)
while 1:
    n = int(sys.stdin.readline())
    ans = 0
    if n == 0:
        break
    solve(n)
"""

#2003_D
"""
import sys
def root(x,par):
    if par[x] == x:
        return x
    par[x] = root(par[x],par)
    return par[x]

def unite(x,y,par,rank):
    x = root(x,par)
    y = root(y,par)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

def solve(n):
    p = [[float(x) for x in sys.stdin.readline().split()] for i in range(n)]
    v = []
    for i in range(n):
        for j in range(i):
            xi,yi,zi,ri = p[i]
            xj,yj,zj,rj = p[j]
            d = max(0,((xi-xj)**2+(yi-yj)**2+(zi-zj)**2)**0.5-(ri+rj))
            v.append((i,j,d))
    par = [i for i in range(n)]
    rank = [0]*n
    v.sort(key = lambda x:x[2])
    ans = 0
    for x,y,d in v:
        if root(x,par) != root(y,par):
            unite(x,y,par,rank)
            ans += d
    print("{:.3f}".format(round(ans,3)))

while 1:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    solve(n)
"""

#2009_D
"""
import sys
from heapq import heappop,heappush
from collections import defaultdict
def solve(n,m):
    s,g = [int(x) for x in sys.stdin.readline().split()]
    s -= 1
    g -= 1
    e = [[] for i in range(n)]
    for i in range(m):
        a,b,d,c = [int(x) for x in sys.stdin.readline().split()]
        a -= 1
        b -= 1
        e[a].append((b,d,c))
        e[b].append((a,d,c))
    dist = defaultdict(lambda : float("inf"))
    dist[(s,0,-1)] = 0
    q = [(0,s,0,-1)]
    while q:
        dx,x,v,p = heappop(q)
        if x == g and v == 1:
            print(dx)
            return
        for i in range(-1,2):
            v_ = v+i
            if v_ < 1 :continue
            for y,d,c in e[x]:
                if p == y:
                    continue
                if v_ > c:
                    continue
                z = d/v_
                if dx+z < dist[(y,v_,x)]:
                    dist[(y,v_,x)] = dx+z
                    heappush(q,(dist[(y,v_,x)],y,v_,x))
    print("unreachable")
    return

while 1:
    n,m = [int(x) for x in sys.stdin.readline().split()]
    if n == 0:
        break
    solve(n,m)
"""

#2016_D
import sys
def solve(n):
    w = [int(x) for x in sys.stdin.readline().split()]
    dp = [[0]*(n+1) for i in range(n+1)]
    for le in range(n+1):
        for l in range(n):
            r = l+le
            if r > n:break
            if not (r-l)%2 and abs(w[l]-w[r-1]) < 2:
                if dp[l+1][r-1] == r-l-2:
                    dp[l][r] = r-l
                    continue
            for k in range(l+1,r):
                if dp[l][k] + dp[k][r] > dp[l][r]:
                    dp[l][r] = dp[l][k] + dp[k][r]
    print(dp[0][n])
while 1:
    n = int(sys.stdin.readline())
    if not n:
        break
    solve(n)

Submission status: Accepted

Solution code:
from functools import lru_cache
while True:
    N = int(input())
    if N==0:
        break
    W = list(map(int, input().split()))
    assert len(W) == N


    @lru_cache(maxsize=None)
    def solve(l, r):
        assert l<=r
        if (r-l)%2==1:
            return False
        if r-l==2:
            return abs(W[l]-W[l+1])<=1

        if solve(l+1, r-1) and abs(W[l]-W[r-1])<=1:
            return True
        for i in range(l+2, r, 2):
            if solve(l, i) and solve(i, r):
                return True
        return False
        # return (solve(l, r-2) and solve(r-2, r)) \
        #     or (solve(l, l+2) and solve(l+2, r)) \
        #     or


    dp = [0]*(N+1)
    for i in range(1, N+1):
        ma = 0
        for j in range(i-1, -1, -1):
            ma = max(ma, dp[j]+solve(j, i)*(i-j))
            #if (j-i)%2==0:
            #    print(f"j={j}, i={i}, dp={solve(j,i)}")
        dp[i] = ma
    #print(dp)
    print(dp[-1])

Submission status: Accepted

Solution code:
n=int(input())
while n!=0:
    w=list(map(int,input().split()))
    check=[[False]*n for i in range(n)]
    for i in range(n-1):
        if abs(w[i+1]-w[i])<=1:
            check[i][i+1]=True
    for i in range(3,n,2):
        for j in range(n-i):
            for k in range(j+1,j+i):
                if check[j][j+i]==False and check[j][k] and check[k+1][j+i]:
                    check[j][j+i]=True
                    break
            if check[j][j+i]==False and abs(w[j]-w[j+i])<=1 and check[j+1][j+i-1]:
                check[j][j+i]=True
    dp=[0]*(n+1)
    for k in range(n):
        for m in range(k):
            if check[m][k]:
                dp[k]=max(dp[k],dp[m-1]+k-m+1)
        dp[k]=max(dp[k],dp[k-1])
    print(dp[n-1])
    n=int(input())

Submission status: Runtime Error

Solution code:
n = int(input())
if n == 0:
    break
w = list(map(int, input().split()))
dp = [[-1 for j in range(n + 1)] for i in range(n + 1)]


def rec(l, r):
    # 既に計算済み？
    if dp[l][r] != -1:
        return dp[l][r]

    # これ以上取り除けない？
    if abs(l - r) <= 1:
        return 0

    res = 0
    # パターン1.
    if abs(w[l] - w[r - 1]) <= 1 and rec(l + 1, r - 1) == r - l - 2:
        res = r - l

    # パターン２.区間を分ける
    for mid in range(l + 1, r - 1):
        res = max(res, rec(l, mid) + rec(mid, r))

    dp[l][r] = res
    return res


print(rec(0, n))

Submission status: Runtime Error

Solution code:
while True:
    N = int(input())
    if not N:
        break
    W = [int(x) for x in input().split()]
    dp = [[0] * N for _ in range(N)]
    for w in range(2, N + 1):
        for left in range(N - w + 1):
            # [left, right]
            right = left + w - 1
            for mid in range(left + 1, right):
                dp[left][right] = max(dp[left][right], dp[left][mid] + dp[mid + 1][right])
            if right - left - 1 == dp[left + 1][right - 1] and abs(W[left] - W[right]) <= 1:
                dp[left][right] = right - left + 1
    print(dp[0][N-1])

Submission status: Runtime Error

Solution code:
while True:
    N = int(input())
    if not N:
        break
    W = [int(x) for x in input().split()]
    dp = [[0] * N for _ in range(N)]
    for w in range(2, N + 1):
        for left in range(N - w + 1):
            # [left, right]
            right = left + w - 1
            if right - left - 1 == dp[left + 1][right - 1] and abs(W[left] - W[right]) <= 1:
                dp[left][right] = right - left + 1
                continue
            for mid in range(left + 1, right):
                dp[left][right] = max(dp[left][right], dp[left][mid] + dp[mid + 1][right])
    print(dp[0][N-1])

Submission status: Runtime Error

Solution code:
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
while True:
    N = int(input())
    if not N:
        break
    W = [int(x) for x in input().split()]
    dp = [[0] * N for _ in range(N)]
    for w in range(2, N + 1):
        for left in range(N - w + 1):
            # [left, right]
            right = left + w - 1
            if right - left - 1 == dp[left + 1][right - 1] and abs(W[left] - W[right]) <= 1:
                dp[left][right] = right - left + 1
                continue
            for mid in range(left + 1, right):
                dp[left][right] = max(dp[left][right], dp[left][mid] + dp[mid + 1][right])
    print(dp[0][N-1])

Submission status: Runtime Error

Solution code:
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
while True:
    N = int(input())
    if not N:
        break
    W = [int(x) for x in input().split()]
    dp = [[0] * N for _ in range(N)]
    for i in range(N-1):
        if abs(W[i] - W[i + 1]) <= 1:
            dp[i][i + 1] = 2
    for w in range(3, N + 1):
        for left in range(N - w + 1):
            # [left, right]
            right = left + w - 1
            if right - left - 1 == dp[left + 1][right - 1] and abs(W[left] - W[right]) <= 1:
                dp[left][right] = right - left + 1
                continue
            for mid in range(left + 1, right):
                m = dp[left][mid] + dp[mid + 1][right]
                if m > dp[left][right]:
                    dp[left][right] = m
    print(dp[0][N-1])

Submission status: Runtime Error

Solution code:
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
ans = []
idx = [x for x in reversed(range(300))]
for i in range(299):
    idx[i + 1] += idx[i]

def dec(l, r):
    return idx[l] + r - l

while True:
    N = int(input())
    if not N:
        break
    W = [int(x) for x in input().split()]
    dp = [0] * (N * (N + 1) // 2)
    for i in range(N-1):
        if abs(W[i] - W[i + 1]) <= 1:
            dp[dec(i, i + 1)] = 2
    for w in range(3, N + 1):
        for left in range(N - w + 1):
            # [left, right]
            right = left + w - 1
            if w - 2 == dp[dec(left + 1, right - 1)] and abs(W[left] - W[right]) <= 1:
                dp[dec(left, right)] = w
                continue
            for mid in range(left + 1, right):
                m = dp[dec(left, mid)] + dp[dec(mid + 1, right)]
                if m > dp[dec(left, right)]:
                    dp[dec(left, right)] = m
    print(dp[dec(0, N-1)])

Submission status: Runtime Error

Solution code:
def shot(i, daruma):
    if i >= len(daruma):
        results.append(n - len(daruma))
        return

    string = "_".join(map(str, daruma))
    if dp[i].get(string):
        return

    dp[i][string] = True
    shot(i + 1, daruma[:])
    if abs(daruma[i - 1] - daruma[i]) <= 1:
        del daruma[i]
        del daruma[i - 1]
        shot(1, daruma[:])

dp = []
results = []
n = 0
def resolve():
    global results
    global n
    global dp
    n = int(input())
    if n == 0: return False

    dp = [{} for x in range(n)]
    daruma = list(map(int, input().split()))
    results = []
    shot(1, daruma[:])
    print(max(results))
    return True


while resolve(): pass

Submission status: Runtime Error

Solution code:
def f(daruma):
	global flag, min
	if (flag):
		return

	length = len(daruma)
	if (daruma == 0 or daruma == 1):
		print(n - length)
		flag = true
		return

	for i in range(length-1):
		diff = abs(daruma[i] - daruma[i+1])
		if (diff < 2):
			kari_daruma = daruma[:i] + daruma[i+2:]
			f(kari_daruma)
	else:
		min = (min if min <= length else length)
		return

while 1:
	count = 0
	flag = False
	
	n = int(input())
	if (n == 0):
		break
	min = n
	daruma = list(map(int, input().split()))
	f(daruma)
	print(n - min)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
def f(daruma):
	global flag, min
	if (flag):
		return

	length = len(daruma)
	if (daruma == 0 or daruma == 1):
		print(n - length)
		flag = true
		return

	for i in range(length-1):
		diff = abs(daruma[i] - daruma[i+1])
		if (diff < 2):
			kari_daruma = daruma[:i] + daruma[i+2:]
			f(kari_daruma)
	else:
		min = (min if min <= length else length)
		return

while 1:
	count = 0
	flag = False
	
	n = int(input())
	if (n == 0):
		break
	min = n
	daruma = list(map(int, input().split()))
	f(daruma)
	print(n - min)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

def f(daruma):
	global flag, min
	if (flag):
		return

	length = len(daruma)
	if (daruma == 0 or daruma == 1):
		print(n - length)
		flag = true
		return

	for i in range(length-1):
		diff = abs(daruma[i] - daruma[i+1])
		if (diff < 2):
			kari_daruma = daruma[:i] + daruma[i+2:]
			f(kari_daruma)
	else:
		min = (min if min <= length else length)
		return

while 1:
	count = 0
	flag = False
	
	n = int(input())
	if (n == 0):
		break
	min = n
	daruma = list(map(int, input().split()))
	f(daruma)
	print(n - min)