HDU 1069 Monkey and Banana(DP)

제목 링크
이 문제의 뜻을 이해할 때 난이도가 별로 없어요. 백련상에 중국어판 데이터가 똑같아요.일반 O(n^2) DP.

 1 #include <stdio.h>

 2 #include <string.h>

 3 #include <stdlib.h>

 4 int o[2000];

 5 struct node

 6 {

 7     int x,y;

 8     int h;

 9 }p[2000];

10 int cmp(const void *a,const void *b)

11 {

12     return (*(struct node *)a).x >(*(struct node *)b).x ? 1:-1;

13 }

14 int main()

15 {

16     int n,i,j,num = 0,sv,ev,w,max;

17     while(scanf("%d",&n)!=EOF)

18     {

19         if(!n) break;

20         num ++;

21         memset(p,0,sizeof(p));

22         memset(o,0,sizeof(o));

23         for(i = 1;i <= n;i ++)

24         {

25             scanf("%d%d%d",&sv,&ev,&w);

26             p[6*(i-1)].x = sv;

27             p[6*(i-1)].y = ev;

28             p[6*(i-1)].h = w;

29             p[6*(i-1)+1].x = ev;

30             p[6*(i-1)+1].y = sv;

31             p[6*(i-1)+1].h = w;

32             p[6*(i-1)+2].x = ev;

33             p[6*(i-1)+2].y = w;

34             p[6*(i-1)+2].h = sv;

35             p[6*(i-1)+3].x = w;

36             p[6*(i-1)+3].y = sv;

37             p[6*(i-1)+3].h = ev;

38             p[6*(i-1)+4].x = w;

39             p[6*(i-1)+4].y = ev;

40             p[6*(i-1)+4].h = sv;

41             p[6*(i-1)+5].x = sv;

42             p[6*(i-1)+5].y = w;

43             p[6*(i-1)+5].h = ev;

44         }

45         qsort(p,6*n,sizeof(p[0]),cmp);

46         o[0] = p[0].h;

47         for(i = 1;i <= n*6-1;i ++)

48         {

49             max = 0;

50             for(j = 0;j <= i-1;j ++)

51             {

52                 if(p[i].x > p[j].x&&p[i].y > p[j].y)

53                 {

54                     if(max < o[j])

55                     max = o[j];

56                 }

57                 o[i] = max+p[i].h;

58             }

59         }

60         max = 0;

61         for(i = 0;i <= 6*n-1;i ++)

62         {

63             if(max < o[i])

64             max = o[i];

65         }

66         printf("Case %d: maximum height = %d
",num,max);

67     }

68     return 0;

69 }