hdu 1069 최장 상승자 서열 변형

모든 Block은 무한히 여러 개가 있기 때문에 (x, y,z) 등가는 (x, y,z)+(x,z,y)+(y,z,x) 이 세 가지 Block이다.
그런 다음 사각형 중첩처럼 해답을 구한다. 단지 상태 이동 방정식은 다음과 같다.
　　dp[i] = max( dp[i], dp[j] + z[i] );
코드는 다음과 같습니다.

 1 #include <algorithm>

 2 #include <cstdio>

 3 using namespace std;

 4 

 5 const int N = 100;

 6 int dp[N];

 7 

 8 struct Node

 9 {

10     int x, y, z;

11     bool operator < ( const Node & o ) const

12     {

13         if ( x != o.x ) return x < o.x;

14         return y < o.y;

15     }

16     Node(){}

17     Node( int _x, int _y, int _z )

18     {

19         x = _x, y = _y, z = _z;

20     }

21     void standard()

22     {

23         if ( x > y ) swap( x, y );

24     }

25 } node[N];

26 

27 int main ()

28 {

29     int n, _case = 1;

30     while ( scanf("%d", &n), n )

31     {

32         for ( int i = 0; i < n; i++ )

33         {

34             int x, y, z;

35             scanf("%d%d%d", &x, &y, &z);

36             node[i * 3] = Node( x, y, z );

37             node[i * 3].standard();

38             node[i * 3 + 1] = Node( x, z, y );

39             node[i * 3 + 1].standard();

40             node[i * 3 + 2] = Node( y, z, x );

41             node[i * 3 + 2].standard();

42         }

43         sort( node, node + 3 * n );

44         int ans = -1;

45         for ( int i = 0; i < 3 * n; i++ )

46         {

47             dp[i] = node[i].z;

48             for ( int j = 0; j < i; j++ )

49             {

50                 if ( node[j].x < node[i].x && node[j].y < node[i].y )

51                 {

52                     dp[i] = max( dp[i], dp[j] + node[i].z );

53                 }

54             }

55             ans = max( ans, dp[i] );

56         }

57         printf("Case %d: maximum height = %d
", _case++, ans);

58     }

59     return 0;

60 }