UVA 103 Stacking Boxes(dp + DAG의 최장 경로 + 기억형 검색)
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 (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 such that each box nests in box ( .
A box D = ( ) nests in a box E = ( ) if there is some rearrangement of the 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 = ( ) nests in box E = ( ) if there is a permutation of such that ( ) ``fits'' in ( ) i.e., if for all .
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 line in the sequence ( ) gives the measurements for the 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비트 상자를 정한다.몇 층까지 할 수 있냐고 물어보셨어요.
사고방식: 나는 기억화 검색을 사용한다.dp수 그룹으로 몇 개를 기록했다.만약 검색 과정에서 작은 것을 직접 고려하지 않는다면
코드:#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int n, m, i, j, Max, dp[35], way[35], save[35];
struct Box {
int d[15];
} b[35];
int judge(int small, int big) {
for (int i = 0; i < m; i ++)
if (b[small].d[i] >= b[big].d[i])
return 0;
return 1;
}
void dfs(int now, int num) {
for (int i = 1; i <= n; i ++) {
if (i != now && judge(now, i) && dp[i] < num + 1) {//dp[i] < num + 1 。
dp[i] = num + 1;
save[num] = i;
dfs(i, num + 1);
}
}
if (Max < num) {
Max = num;
for (int j = 0; j < num; j ++)
way[j] = save[j];
}
}
int main() {
while (~scanf("%d%d", &n, &m)) {
Max = 0;
memset(dp, 0, sizeof(dp));
for (i = 1; i <= n; i ++) {
for (j = 0; j < m; j ++) {
scanf("%d", &b[i].d[j]);
}
sort(b[i].d, b[i].d + m);
}
dfs(0, 0);
printf("%d
", Max);
for (i = 0; i < Max - 1; i ++)
printf("%d ", way[i]);
printf("%d
", way[Max - 1]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
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
5
3 1 2 4 5
4
7 2 5 6
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int n, m, i, j, Max, dp[35], way[35], save[35];
struct Box {
int d[15];
} b[35];
int judge(int small, int big) {
for (int i = 0; i < m; i ++)
if (b[small].d[i] >= b[big].d[i])
return 0;
return 1;
}
void dfs(int now, int num) {
for (int i = 1; i <= n; i ++) {
if (i != now && judge(now, i) && dp[i] < num + 1) {//dp[i] < num + 1 。
dp[i] = num + 1;
save[num] = i;
dfs(i, num + 1);
}
}
if (Max < num) {
Max = num;
for (int j = 0; j < num; j ++)
way[j] = save[j];
}
}
int main() {
while (~scanf("%d%d", &n, &m)) {
Max = 0;
memset(dp, 0, sizeof(dp));
for (i = 1; i <= n; i ++) {
for (j = 0; j < m; j ++) {
scanf("%d", &b[i].d[j]);
}
sort(b[i].d, b[i].d + m);
}
dfs(0, 0);
printf("%d
", Max);
for (i = 0; i < Max - 1; i ++)
printf("%d ", way[i]);
printf("%d
", way[Max - 1]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.