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: Wrong Answer

Solution code:
n = int(input())
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
    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: Wrong Answer

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


    @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
        return (solve(l, r-2) and solve(r-2, r)) \
            or (solve(l, l+2) and solve(l+2, r)) \
            or (solve(l+1, r-1) and abs(W[l]-W[r-1])<=1)


    dp = [0]*(N+1)
    for i in range(N+1):
        ma = 0
        for j in range(i-1, -1, -1):
            ma = max(ma, dp[j]+solve(j, i)*(i-j))
        dp[i] = ma

    print(dp[-1])

Submission status: Wrong Answer

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


    @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
        return (solve(l, r-2) and solve(r-2, r)) \
            or (solve(l, l+2) and solve(l+2, r)) \
            or (solve(l+1, r-1) and abs(W[l]-W[r-1])<=1)


    dp = [0]*(N+1)
    for i in range(N+1):
        ma = 0
        for j in range(i-1, -1, -1):
            ma = max(ma, dp[j]+solve(j, i)*(i-j))
        dp[i] = ma

    print(dp[-1])

Submission status: Wrong Answer

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
        return (solve(l, r-2) and solve(r-2, r)) \
            or (solve(l, l+2) and solve(l+2, r)) \
            or (solve(l+1, r-1) and abs(W[l]-W[r-1])<=1)


    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))
        dp[i] = ma

    print(dp[-1])

Submission status: Wrong Answer

Solution code:
def isvalid(a, b):
    return abs(a - b) < 2
while 1:
    n = input()
    if n==0:
        break
    W = map(int, raw_input().split())
    dp = [[0]*n for i in xrange(n)]
    for i in xrange(1, n):
        if isvalid(W[i], W[i-1]):
            dp[i-1][i] = 1
        for j in xrange(i):
            # [i,j]
            if j+2 < i and isvalid(W[j], W[j+1]) and dp[j+2][i]:
                # ab[...]
                dp[j][i] = 1
            elif j < i-2 and isvalid(W[i-1], W[i]) and dp[j][i-2]:
                # [...]ab
                dp[j][i] = 1
            elif j+1 < i-1 and isvalid(W[j], W[i]) and dp[j+1][i-1]:
                # a[...]b
                dp[j][i] = 1
            else:
                # [...][...]
                for k in xrange(j+1, i-1):
                    if dp[j][k] and dp[k+1][i]:
                        dp[j][i] = 1
                        break
    res = [0]*n
    for i in xrange(n):
        r = res[i-1]
        for j in xrange(i):
            if dp[j][i]:
                r = max(r, res[j-1]+(i-j+1))
        res[i] = r
    print res[n-1]

Submission status: Wrong Answer

Solution code:
def isvalid(a, b):
    return abs(a - b) < 2
while 1:
    n = input()
    if n==0:
        break
    W = map(int, raw_input().split())
    dp = [[0]*n for i in xrange(n)]
    for i in xrange(n-1):
        if isvalid(W[i], W[i+1]):
            dp[i][i+1] = 1
    for l in xrange(1, n+1):
        for j in xrange(n-l):
            i = j+l
            # [i,j]
            if j+2 < i and isvalid(W[j], W[j+1]) and dp[j+2][i]:
                # ab[...]
                dp[j][i] = 1
            elif j < i-2 and isvalid(W[i-1], W[i]) and dp[j][i-2]:
                # [...]ab
                dp[j][i] = 1
            elif j+1 < i-1 and isvalid(W[j], W[i]) and dp[j+1][i-1]:
                # a[...]b
                dp[j][i] = 1
            else:
                # [...][...]
                for k in xrange(j+1, i-1):
                    if dp[j][k] and dp[k+1][i]:
                        dp[j][i] = 1
                        print j, k, k+1, i
                        break
    res = [0]*n
    for i in xrange(n):
        r = res[i-1]
        for j in xrange(i):
            if dp[j][i]:
                r = max(r, res[j-1]+(i-j+1))
        res[i] = r
    print res[n-1]

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(n):
        a = LI()

        m = {}
        def _f(a):
            l = len(a)
            if l < 2:
                return 0
            k = tuple(a)
            if k in m:
                return m[k]
            r = 0
            for i in range(len(a)-1):
                if abs(a[i]-a[i+1]) >= 2:
                    continue
                t = _f(a[:i] + a[i+2:]) + 2
                if r < t:
                    r = t
            m[k] = r
            return r

        return _f(a)

    while True:
        n = I()
        if n == 0:
            break
        rr.append(f(n))

    return '\n'.join(map(str, rr))



print(main())

Submission status: Time Limit Exceeded

Solution code:
while True:
    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: Time Limit Exceeded

Solution code:
while True:
  n = int(input())
  if n == 0:
    break
  wlst = list(map(int, input().split()))
  dp = [[0] * n for _ in range(n + 1)]
  
  def check(left1, right1, left2, right2, cnt):
    if left1 > right1 and left2 > right2: return cnt
    if left1 > right1:return dp[right2 - left2 + 1][left2] + cnt
    if left2 > right2:return dp[right1 - left1 + 1][left1] + cnt
    ret = cnt + dp[right1 - left1 + 1][left1] + dp[right2 - left2 + 1][left2]
    if abs(wlst[right1] - wlst[left2]) <= 1:
      ret = max(ret, check(left1, right1 - 1, left2 + 1, right2, cnt + 1))
    if right1 - left1 + 1 >= 2 and dp[2][right1 - 1]:
      ret = max(ret, check(left1, right1 - 2, left2, right2, cnt + 1))
    if right2 - left2 + 1 >= 2 and dp[2][left2]:
      ret = max(ret, check(left1, right1, left2 + 2, right2, cnt + 1))
    return ret
  
  for length in range(2, n + 1):
    for left in range(n - length + 1):
      for k in range(length - 1):
        dp[length][left] = max(dp[length][left], check(left, left + k, left + k + 1, left + length - 1, 0))
  
  print(dp[n][0] * 2)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import sys
from collections import Counter


input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


def inpl(): return list(map(int, input().split()))


def solve(n, W):
    dp = [[0] * (n + 1) for _ in range(n + 1)]

    def rec(l, r):
        if dp[l][r] != 0:
            return dp[l][r]

        if abs(r - l) <= 1:
            return 0

        res = 0
        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

    return rec(0, n)


while 1:
    n = int(input())
    W = inpl()
    if n == 0:
        exit()
    print(solve(n, W))

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import sys


input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


def inpl(): return list(map(int, input().split()))


def solve(n, W):
    dp = [[0] * (n + 1) for _ in range(n + 1)]

    for w in range(2, n + 1):
        for l in range(n):
            r = l + w
            if r > n: continue

            if dp[l + 1][r - 1] == w - 2 and abs(W[l] - W[r - 1]) <= 1:
                dp[l][r] = w

            for mid in range(l, r):
                dp[l][r] = max(dp[l][r], dp[l][mid] + dp[mid][r])
            # print(l, r, dp)

    return dp[0][n]


while 1:
    n = int(input())
    W = inpl()
    if n == 0:
        exit()
    print(solve(n, W))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(n):
        a = LI()
        l = len(a)
        s = set()
        r = 0
        for i in range(l-1):
            if abs(a[i] - a[i+1]) < 2:
                s.add((i,i+1))
        for i in range(4, l+1):
            for j in range(l-i+1):
                k = j + i - 1
                if (j+1, k-1) in s and abs(a[j] - a[k]) < 2:
                    s.add((j,k))
                    continue
                for m in range(j+2,k,2):
                    if (j,m-1) in s and (m,k) in s:
                        s.add((j,k))
                        break

        m = {}
        m[l] = 0
        def _f(i):
            if i in m:
                return m[i]
            r = 0
            for j in range(i,l+1):
                t = _f(j+1)
                if (i,j) in s:
                    t += j - i + 1
                if r < t:
                    r = t
            m[i] = r
            return r
        return _f(0)

    while True:
        n = I()
        if n == 0:
            break
        rr.append(f(n))

    return '\n'.join(map(str, rr))



print(main())

Submission status: Accepted

Solution code:
def main():
  while True:
    n = int(input())
    if n == 0:
      break
    wlst = list(map(int, input().split()))
    connect = [[None] * n for _ in range(n)]
    for i in range(n):
      for j in range(n):
        connect[i][j] = abs(wlst[i] - wlst[j]) <= 1
    
    max_lst = [[False] * (n + 1) for _ in range(n + 1)]
    for i in range(n + 1):
      max_lst[0][i] = True
    
    dp = [[0] * n for _ in range(n + 1)]
    
    def check(length, left):
      ret = dp[length - 1][left]
      for k in range(length - 1, 0, -2):
        if not max_lst[length - k - 1][left + k]:continue
        if connect[left + k - 1][left + length - 1]:
          temp = length - k + 1 + dp[k - 1][left]
          if ret < temp:
            ret = temp
      return ret
    
    for length in range(2, n + 1):
      for left in range(n - length + 1):
        dp[length][left] = check(length, left)
        if dp[length][left] == length:
          max_lst[length][left] = True
    
    print(dp[n][0])

main()

Submission status: Accepted

Solution code:
def isvalid(a, b):
    return abs(a - b) < 2
while 1:
    n = input()
    if n==0:
        break
    W = map(int, raw_input().split())
    dp = [[0]*n for i in xrange(n)]
    for i in xrange(n-1):
        if isvalid(W[i], W[i+1]):
            dp[i][i+1] = 1
    for l in xrange(1, n+1):
        for j in xrange(n-l):
            i = j+l
            # [i,j]
            if j+2 < i and isvalid(W[j], W[j+1]) and dp[j+2][i]:
                # ab[...]
                dp[j][i] = 1
            elif j < i-2 and isvalid(W[i-1], W[i]) and dp[j][i-2]:
                # [...]ab
                dp[j][i] = 1
            elif j+1 < i-1 and isvalid(W[j], W[i]) and dp[j+1][i-1]:
                # a[...]b
                dp[j][i] = 1
            else:
                # [...][...]
                for k in xrange(j+1, i-1):
                    if dp[j][k] and dp[k+1][i]:
                        dp[j][i] = 1
                        break
    res = [0]*n
    for i in xrange(n):
        r = res[i-1]
        for j in xrange(i):
            if dp[j][i]:
                r = max(r, res[j-1]+(i-j+1))
        res[i] = r
    print res[n-1]

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

ans = []
while True:
    N = int(input())
    if N == 0: break
    W = list(map(int, input().split()))
    # dp[i][j]: iからjのブロックを全て除外可能か
    dp = [[False]*N for _ in range(N)]
    for i in range(N-1):
        if abs(W[i]-W[i+1]) <= 1:
            dp[i][i+1] = True
    for d in range(4, N+1):
        for i in range(N-d+1):
            j = i+d-1
            for k in range(i, j):
                if dp[i][k] and dp[k+1][j]:
                    dp[i][j] = True
            if abs(W[i]-W[j]) <= 1 and dp[i+1][j-1]:
                dp[i][j] = True
    # dp2[i]: iまでで除外可能なブロックの最大値(1-indexed)
    dp2 = [0]*(N+1)
    for i in range(N):
        for j in range(i+1, N):
            if dp[i][j]:
                dp2[j+1] = max(dp2[j+1], dp2[i]+j-i+1)
        dp2[i+1] = max(dp2[i+1], dp2[i])
    ans.append(dp2[N])
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
def solve(n,w):
    dp=[[0]*(n+1) for _ in range(n+1)]
    for kukan in range(2,n+1):
        for l in range(0,n+1-kukan):
            r=l+kukan
            #decide dp[l][l+kukan]
            if (kukan-2)%2==0:
                if abs(w[l]-w[r-1])<=1 and dp[l+1][r-1]==r-l-2:
                    dp[l][r]=dp[l+1][r-1]+2
                    continue
            for i in range(l+1,r):
                if dp[l][r]<(dp[l][i]+dp[i][r]):
                    dp[l][r]=dp[l][i]+dp[i][r]
    return dp[0][n]
            

n=int(input())
while(n!=0):
    w=list(map(int,input().split()))
    print(solve(n,w))
    n=int(input())

Submission status: Accepted

Solution code:
def solve(n,lst):
    #i行j列はjから連続したi個のうち落とせる個数の最大値
    dp=[[0]*n for _ in range(n+1)]

    #initialize
    for j in range(n-1):
        if abs(lst[j]-lst[j+1])<=1 : dp[2][j]=2
    

    #真ん中2*i個が抜けて上下を落とせる場合と2*(i+1)個を複数の部分に分けて落とせる場合の2通りが考えられる
    for i in range(3,n+1):
        for j in range(n-i+1):
            mx=0
            if i%2==0:
                if abs(lst[j]-lst[j+i-1])<=1:
                    if dp[i-2][j+1]==i-2:
                        dp[i][j]=i
                        continue
                mx=dp[i-2][j+1]                
                for k in range(2,i,2):
                    if mx<dp[k][j]+dp[i-k][j+k]:
                        mx=dp[k][j]+dp[i-k][j+k]
                        if mx==i:break
            else :
                for k in range(1,i,2):
                    if mx<dp[k][j]+dp[i-k][j+k]:
                        mx=dp[k][j]+dp[i-k][j+k]                
            dp[i][j]=mx
    print(dp[n][0])        
    #print(dp) 

                

while 1:
    n=int(input())
    if n==0 : break
    lst=tuple(map(int,input().split()))
    solve(n,lst)

Submission status: Accepted

Solution code:
import sys


def main():
    while True:
        n = int(input())

        # nが0なら処理終わり
        if n == 0:
            sys.exit()

        arr = list(map(int, input().split()))

        # dpテーブル
        dp = [[0] * n for _ in range(n)]

        # dはdistance。lとrが1〜n-1離れている場合を順に考えていく
        for d in range(1, n):

            # distanceに応じてleftのレンジが変化する
            for l in range(n - d):

                # rは当然left+distance
                r = l + d

                # もしdistanceが奇数なら、1個内側を見ればいい
                if d % 2 == 1:

                    # left, rightの内側が全部叩き出せる場合
                    if dp[l + 1][r - 1] == d - 1 and abs(arr[l] - arr[r]) <= 1:
                        dp[l][r] = dp[l + 1][r - 1] + 2

                    # 叩けないブロックがある場合はワーシャルフロイドっぽく解く
                    else:
                        for k in range(l + 1, r):
                            tmp = dp[l][k] + dp[k + 1][r]
                            if tmp > dp[l][r]:
                                dp[l][r] = tmp

                # もしdistanceが偶数なら、大きい方を採用するだけ
                else:
                    dp[l][r] = max(dp[l + 1][r], dp[l][r - 1])

        print(dp[0][-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

while True:
    n=int(input())
    if n==0:
        break
    w = [int(x) for x in sys.stdin.readline().split()]

    dp=[[0]*n for i in range(n)] 

    for l in range(n-1):
        r=l+1
        if abs(w[l]-w[r])<2:
            dp[l][r]=2
        
    for i in range(2,n):
        if i%2==1:
            for l in range(n-i):
                r=l+i
                if dp[l+1][r-1]==r-l-1 and abs(w[l]-w[r])<2:
                    dp[l][r]=r-l+1
                else:
                    for lr in range(l+1,r):
                        if dp[l][r]< dp[l][lr]+dp[lr+1][r]:
                            dp[l][r]=dp[l][lr]+dp[lr+1][r]
        else:
            for l in range(n-i):
                r=l+i
#                dp[l][r]=max(dp[l][r],dp[l+1][r],dp[l][r-1])
                if dp[l][r]<dp[l+1][r]:
                    dp[l][r]=dp[l+1][r]
                if dp[l][r]<dp[l][r-1]:
                    dp[l][r]=dp[l][r-1]
    print(dp[0][n-1])

Submission status: Accepted

Solution code:
def main(n):
    a = list(map(int, input().split()))
    dp = [[0] * (n+1) for i in range(n)]
    # 区間[l,r)の最大落とせる個数
    for i in range(n - 1):
        if abs(a[i] - a[i + 1]) <= 1:
            dp[i][i + 2] = 2
            # 隣り合う達磨weightが1以内のペアをdpに記録
    for i in range(2, n): # 区間の広さ, 最大で0番目とn-1番目の差
        for l in range(n-i): # 左側のとれる値は区間の広さに依存
            r = i+l+1 # 右側は上記2変数から計
            if abs(a[l] - a[r-1]) <= 1: # 今見ている左端と右端がweight 1以内の時
                if dp[l+1][r-1] == r-l-2: # 左右1個ずつ内側の最大落とせる個数が「全部落とせる」だったとき
                    dp[l][r] = r-l # dp[l][r]は左右端を追加して記録
                    continue
            res = dp[l+1][r-1] # とりあえず現在の左右1個ずつ内側の値を記録
            for li in range(l+1, r): # lとrの間のどこかで区切って「lから区切り」「区切りからr」までの和を出す
                tmp = dp[l][li] + dp[li][r] # 区間[l, li) と 区間[li, r)のdp和
                if res < tmp: #区切った場所が最大値を更新するのであればresを更新
                    res = tmp
            dp[l][r] = res
    print(dp[0][n]) # 左端 0 から右端 n-1 までの最大値を出す

if __name__ == "__main__":
    while 1:
        n = int(input())
        if n:
            main(n)
        else:
            break

Submission status: Accepted

Solution code:
def main(n):
    a = list(map(int, input().split()))
    dp = [[0] * n for i in range(n)]
    for i in range(n - 1):
        if abs(a[i] - a[i + 1]) <= 1:
            dp[i][i + 1] = 2
    for i in range(2, n):
        for l in range(n - i):
            r = i + l
            res = 0
            if abs(a[l] - a[r]) <= 1:
                if dp[l + 1][r - 1] == r - l - 1:
                    dp[l][r] = r - l + 1
                    continue
            res = dp[l + 1][r - 1]
            for li in range(l + 1, r):
                tmp = dp[l][li] + dp[li + 1][r]
                if res < tmp:
                    res = tmp
            dp[l][r] = res
    print(dp[0][n-1])
    def dfs(l, r):
        if l >= r: return 0
        if dp[l][r] != -1: return dp[l][r]
        if abs(a[l] - a[r]) <= 1:
            if dfs(l + 1, r - 1) == r - l - 1:
                dp[l][r] = r - l + 1
                return r - l + 1
        res = 0
        for li in range(l + 1, r):
            tmp = 0
            f = 0
            if dp[l][li] != -1:
                tmp += dp[l][li]
            else:
                tmp += dfs(l, li)
            if dp[li + 1][r] != -1:
                tmp += dp[li + 1][r]
            else:
                tmp += dfs(li + 1, r)
            if res < tmp:
                res = tmp
        dp[l][r] = res
        return res
    # print(dfs(0, n - 1))


if __name__ == "__main__":
    while 1:
        n = int(input())
        if n:
            main(n)
        else:
            break

Submission status: Accepted

Solution code:
# AOJ 1611 ダルマ落とし
# 貰うdp

import sys


def main():
    while True:
        N = int(input())
        if N == 0:
            break
        w = list(map(int, sys.stdin.readline().strip().split()))

        # dp 初期化 -------------------------------------------------
        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

        # dp 更新 ------------------------------------------------------
        for l in range(2, N):
            for i in range(N - l):
                j = i + l

                if l % 2 == 1:
                    if dp[i + 1][j - 1] == l - 1 and (abs(w[i] - w[j]) <= 1):
                        dp[i][j] = l + 1
                        continue

                for k in range(i, j):
                    if dp[i][j] < dp[i][k] + dp[k + 1][j]:
                        dp[i][j] = dp[i][k] + dp[k + 1][j]
                        if dp[i][j] == l:
                            break

        # for i in range(len(dp)):
        #     print(dp[i])

        print(dp[0][-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def func():
    while True:
        N = int(input())
        if N == 0: break
        W = [int(i) for i in input().split()]
        
        dp = [[0]*(N+1) for j in range(N+1)]

        for s in range(2, N+1):
            for l in range(N-s+1):
                r = l + s
                if (s - 2) % 2 == 0:
                    if dp[l+1][r-1] == s-2 and abs(W[l] - W[r-1]) <= 1:
                        dp[l][r] = s
                        continue
                for i in range(l, r+1):
                    if dp[l][r] < dp[l][i] + dp[i][r]:
                        dp[l][r] = dp[l][i] + dp[i][r]

        print(dp[0][N])

if __name__ == "__main__":
    func()

Submission status: Accepted

Solution code:
import sys
#input = lambda: sys.stdin.readline().rstrip()
#区間DP

def main():
  while True:
    n = int(input())
    if(n == 0):
      break
    w = list(map(int, input().split()))
    
    dp = [[0] * (n+1) for _ in range(n+1)]
    
    for gap in range(2,n+1):
      #gapが小さい方から埋めることで漏れをなくす
      for l in range(n-gap+1):
        r = l+gap
        if(dp[l+1][r-1] == gap-2):
          if(abs(w[l]-w[r-1]) <= 1):
            dp[l][r] = gap
            continue
        for k in range(l, r):
          if(dp[l][r] < dp[l][k] + dp[k][r]):
            dp[l][r] = dp[l][k] + dp[k][r]
    print(dp[0][n])
    #print(dp)
    
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

def main():
  while True:
    n = int(input())
    if(n == 0):
      break
    w = list(map(int, input().split()))
    dp = [[0] * (n+1) for _ in range(n+2)]
    for gap in range(2,n+1):
      for l in range(n-gap+1):
        r = l+gap
        if(dp[l+1][r-1] == gap-2):
          if(abs(w[l]-w[r-1]) <= 1):
            dp[l][r] = gap
            continue
        for k in range(l, r):
          if(dp[l][r] < dp[l][k]+dp[k][r]):
            dp[l][r] = dp[l][k]+dp[k][r]
    print(dp[0][n])
    
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    while True:
        n = int(input())
        w = list(map(int, input().split()))
        if n==0:
            break
        else:
            dp = [[0]*(n+1) for _ in range(n+2)]
            # 幅
            for i in range(2, n+1):
                for l in range(n-i+1):
                    r = l+i
                    if dp[l+1][r-1] == i-2:
                        if abs(w[l]-w[r-1])<=1:
                            dp[l][r] = i
                        else:
                            dp[l][r] = i-2
                    for j in range(l, r):
                        if dp[l][j] + dp[j][r] > dp[l][r]:
                            dp[l][r] = dp[l][j] + dp[j][r]

            print(dp[0][-1])        

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
# import sys
# input = lambda: sys.stdin.readline().rstrip()

def resolve():
    while True:
        n = int(input())

        if n == 0:
            exit()
        w = list(map(int, input().split()))
        
        dp = [[0]*(n+1) for _ in range(n+2)]
        for gap in range(2,n+1):
            for l in range(n-gap+1):
                r = l + gap
                if dp[l+1][r-1] == gap-2:
                    if abs(w[l] - w[r-1]) <= 1:
                        dp[l][r] = gap
                    else:
                        dp[l][r] = gap - 2
                for k in range(l,r):
                    if dp[l][k] + dp[k][r] > dp[l][r]:
                            dp[l][r] = dp[l][k] + dp[k][r]
                    # dp[l][r] = max(dp[l][r], dp[l][k] + dp[k][r])
        # for i in range(n):
        #     print(*dp[i])
        print(dp[0][-1])
if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def ti(): return tuple(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

## DP

def solve(N):
    A = ti()
    dp = dp2(0, N, N)

    for i in range(N-1):
        if abs(A[i]-A[i+1]) < 2:
            dp[i][i+1] = 2
    
    for h in range(2, N): #hは(区間の長さ)-1
        for i in range(N):
            if i+h >= N:
                break
            j = i+h
            # 区間の長さが偶数の場合
            if h % 2:
                if abs(A[i]-A[j]) < 2 and dp[i+1][j-1] == h-1:
                    dp[i][j] = h + 1
                    continue
                else:
                    dp[i][j] = max(tuple(dp[i][k]+dp[k+1][j] for k in range(i, j)))
            # 区間の長さが奇数の場合
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        else:
            continue

    print(dp[0][N-1])

while True:
    N = ii()
    if N == 0:
        exit()
    solve(N)

Submission status: Accepted

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