Yuki 497 入れ子の箱 ( DP )

No.497 入れ子の箱 - yukicoder

題意：
給 N 個箱子，用三維各自的長度描述。一個箱子 i 容得下另一個箱子 j 若且唯若 X[ i ] > X[ j ] and Y[ i ] > Y[ j ] and Z[ i ] > Z[ j ]。問最多可以形成多少幾層的箱子。

制約：
1≤N≤1000
1≤Xi,Yi,Zi<1e8

解法：
依最小的長度排序，那麼新的箱子只需要考慮從前面的箱子轉移而來。
dp[ i ]: 第 i 個箱子為最外層時的最大層數。

時間 / 空間複雜度：
O( N^2 ) / O( N )

from collections import defaultdict
from functools import cmp_to_key
N = int( input() )
X = []
Y = []
Z = []
for i in range( N ):
  x, y, z = sorted( list( map( int, input().split() ) ) )
  X.append( x )
  Y.append( y )
  Z.append( z )
ord = sorted( list( i for i in range( N ) ), key = cmp_to_key( lambda x, y: 0 if X[ x ] == X[ y ] else ( X[ x ] - X[ y ] ) // abs( X[ x ] - X[ y ] ) ) )
dp = defaultdict( int )
for i in range( N ):
  best = 0
  for j in range( i ):
    a, b = ord[ i ], ord[ j ]
    if X[ b ] < X[ a ] and Y[ b ] < Y[ a ] and Z[ b ] < Z[ a ]:
      best = max( best, dp[ j ] )
  dp[ i ] = best + 1
ans = 0
for key in dp:
  ans = max( ans, dp[ key ] )
print( ans )