Yuki 497 入れ子の箱 ( DP )
題意:
給 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 )