程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVa 103,uva103

UVa 103,uva103

編輯:C++入門知識

UVa 103,uva103


題目來源:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=39

 

 Stacking Boxes 

 

 

 

Background

 

Some concepts in Mathematics and Computer Science are simple in one or two dimensions but become more complex when extended to arbitrary dimensions. Consider solving differential equations in several dimensions and analyzing the topology of an n-dimensional hypercube. The former is much more complicated than its one dimensional relative while the latter bears a remarkable resemblance to its ``lower-class'' cousin.

 

 

 

The Problem

 

Consider an n-dimensional ``box'' given by its dimensions. In two dimensions the box (2,3) might represent a box with length 2 units and width 3 units. In three dimensions the box (4,8,9) can represent a box tex2html_wrap_inline40 (length, width, and height). In 6 dimensions it is, perhaps, unclear what the box (4,5,6,7,8,9) represents; but we can analyze properties of the box such as the sum of its dimensions.

 

In this problem you will analyze a property of a group of n-dimensional boxes. You are to determine the longest nesting string of boxes, that is a sequence of boxes tex2html_wrap_inline44 such that each box tex2html_wrap_inline46 nests in box tex2html_wrap_inline48 ( tex2html_wrap_inline50 .

 

A box D = ( tex2html_wrap_inline52 ) nests in a box E = ( tex2html_wrap_inline54 ) if there is some rearrangement of the tex2html_wrap_inline56 such that when rearranged each dimension is less than the corresponding dimension in box E. This loosely corresponds to turning box D to see if it will fit in box E. However, since any rearrangement suffices, box D can be contorted, not just turned (see examples below).

 

For example, the box D = (2,6) nests in the box E = (7,3) since D can be rearranged as (6,2) so that each dimension is less than the corresponding dimension in E. The box D = (9,5,7,3) does NOT nest in the box E = (2,10,6,8) since no rearrangement of D results in a box that satisfies the nesting property, but F = (9,5,7,1) does nest in box E since F can be rearranged as (1,9,5,7) which nests in E.

 

Formally, we define nesting as follows: box D = ( tex2html_wrap_inline52 ) nests in box E = ( tex2html_wrap_inline54 ) if there is a permutation tex2html_wrap_inline62 of tex2html_wrap_inline64 such that ( tex2html_wrap_inline66 ) ``fits'' in ( tex2html_wrap_inline54 ) i.e., if tex2html_wrap_inline70 for alltex2html_wrap_inline72 .

 

 

 

The Input

 

The input consists of a series of box sequences. Each box sequence begins with a line consisting of the the number of boxes k in the sequence followed by the dimensionality of the boxes, n (on the same line.)

 

This line is followed by k lines, one line per box with the n measurements of each box on one line separated by one or more spaces. The tex2html_wrap_inline82 line in the sequence ( tex2html_wrap_inline84 ) gives the measurements for the tex2html_wrap_inline82 box.

 

There may be several box sequences in the input file. Your program should process all of them and determine, for each sequence, which of the k boxes determine the longest nesting string and the length of that nesting string (the number of boxes in the string).

 

In this problem the maximum dimensionality is 10 and the minimum dimensionality is 1. The maximum number of boxes in a sequence is 30.

 

The Output

 

For each box sequence in the input file, output the length of the longest nesting string on one line followed on the next line by a list of the boxes that comprise this string in order. The ``smallest'' or ``innermost'' box of the nesting string should be listed first, the next box (if there is one) should be listed second, etc.

 

The boxes should be numbered according to the order in which they appeared in the input file (first box is box 1, etc.).

 

If there is more than one longest nesting string then any one of them can be output.

 

 

 

Sample Input

 

 

 

5 2
3 7
8 10
5 2
9 11
21 18
8 6
5 2 20 1 30 10
23 15 7 9 11 3
40 50 34 24 14 4
9 10 11 12 13 14
31 4 18 8 27 17
44 32 13 19 41 19
1 2 3 4 5 6
80 37 47 18 21 9

 

 

 

Sample Output

 

 

 

5
3 1 2 4 5
4
7 2 5 6

解題思路:
題目意思:給定n個m維的矩形,問我們能夠嵌套的矩形最多有幾個,輸出個數和嵌套的矩形編號。
代碼:
 1 #include<bits/stdc++.h>
 2 #define inf 0x7fffffff
 3 using namespace std;
 4 typedef long long LL;
 5 
 6 int k,n;
 7 int dp[33],pre[33];
 8 struct node
 9 {
10     int an[13];
11     int id;
12     friend bool operator < (node a,node b)
13     {
14         for (int i=0 ;i<n ;i++)
15         {
16             if (a.an[i] != b.an[i]) return a.an[i] <  b.an[i];
17         }
18     }
19 }arr[33];
20 
21 void printOut(int u)
22 {
23     if (pre[u]!=-1) printOut(pre[u]);
24     if (pre[u]==-1) printf("%d",arr[u].id+1 );
25     else printf(" %d",arr[u].id+1 );
26 }
27 
28 int main()
29 {
30     while (scanf("%d%d",&k,&n)!=EOF)
31     {
32         memset(dp,0,sizeof(dp));
33         memset(pre,-1,sizeof(pre));
34         for (int i=0 ;i<k ;i++)
35         {
36             for (int j=0 ;j<n ;j++)
37                 scanf("%d",&arr[i].an[j]);
38             arr[i].id=i;
39             sort(arr[i].an,arr[i].an+n);
40         }
41         sort(arr,arr+k);
42         for (int i=0 ;i<k ;i++)
43         {
44             int temp=0;
45             for (int j=0 ;j<i ;j++)
46             {
47                 int flag=0;
48                 for (int u=0 ;u<n ;u++)
49                     if (arr[i].an[u]<=arr[j].an[u]) {flag=1;break; }
50                 if (!flag && dp[j]>temp)
51                 {
52                     temp=dp[j];
53                     pre[i]=j;
54                 }
55             }
56             dp[i]=temp+1;
57         }
58         int maxlen=-1,num=0;
59         for (int i=0 ;i<k ;i++)
60         {
61             if (dp[i]>maxlen)
62             {
63                 maxlen=dp[i];
64                 num=i;
65             }
66         }
67         printf("%d\n",maxlen);
68         printOut(num);
69         printf("\n");
70     }
71     return 0;
72 }

 

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved