いちばん高い塔を建てる
3060 ワード
いちばん高い塔を建てる
下に正方形の六面体レンガで塔を建てたいです.塔は下から上へれんがを積んでできている.
以下の条件を満たして最も高い塔を建てるためのプログラムを作成してください.
(条件1)レンガが回らない.すなわち、側面を底部として使用することはできない.
(条件2)底幅が等しい煉瓦も、重量が等しい煉瓦もない.
(条件3)レンガの高さは同じである可能性がある.
(条件4)塔を建てる場合、底の狭いレンガには底の広いレンガを置くことができません.
(条件5)重煉瓦を軽煉瓦の上に置くことはできません.
説明の入力
入力ファイルの最初の行には、入力するレンガの数が表示されます.レンガを最大100枚入力します.
2行目から、各行は、レンガの底の幅、レンガの高さ、および重量の順に正の整数であるレンガに関する情報を与える.
各タイルは入力順に1から連続番号までです.レンガの幅、高さ、および重量が10000以下の自然数.
出力の説明
最初の列で一番高く積み上げられる塔の高さを出力します.
入力
5
25 3 4
4 4 6
9 2 3
16 2 5
1 5 2
しゅつりょく
10
インプリメンテーションコードアルゴリズム
順番を守るという説明がなかったので、広いところから、昇順に並べて、それから(この部分とは思わなかったので、何度も編んで、それから間違った答えが出てきました)
にじゅう
下部のレンガは上部のレンガより大きい必要があるため、条件によって更新(更新時に高さ値に更新)されます.
dy降順ソート後最大値出力
下に正方形の六面体レンガで塔を建てたいです.塔は下から上へれんがを積んでできている.
以下の条件を満たして最も高い塔を建てるためのプログラムを作成してください.
(条件1)レンガが回らない.すなわち、側面を底部として使用することはできない.
(条件2)底幅が等しい煉瓦も、重量が等しい煉瓦もない.
(条件3)レンガの高さは同じである可能性がある.
(条件4)塔を建てる場合、底の狭いレンガには底の広いレンガを置くことができません.
(条件5)重煉瓦を軽煉瓦の上に置くことはできません.
説明の入力
入力ファイルの最初の行には、入力するレンガの数が表示されます.レンガを最大100枚入力します.
2行目から、各行は、レンガの底の幅、レンガの高さ、および重量の順に正の整数であるレンガに関する情報を与える.
各タイルは入力順に1から連続番号までです.レンガの幅、高さ、および重量が10000以下の自然数.
出力の説明
最初の列で一番高く積み上げられる塔の高さを出力します.
入力
5
25 3 4
4 4 6
9 2 3
16 2 5
1 5 2
しゅつりょく
10
インプリメンテーションコード
public class 가장높은탑쌓기 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
Brick[] arr = new Brick[n];
Integer[] dy = new Integer[n];
Arrays.fill(dy,0);
for(int i=0;i<n;i++){
arr[i] = new Brick(in.nextInt(),in.nextInt(),in.nextInt());
}
Arrays.sort(arr);
for(int i=0;i<n;i++){
int maxLength = 0;
for(int j=i;j>=0;j--){
if(arr[i].s<arr[j].s && arr[i].w<arr[j].w){
//현재 보다 넓이가 넓고 무게가 무거운 경우
if(maxLength<=dy[j]){
maxLength = dy[j];
}
}
}
dy[i] = maxLength + arr[i].h;
}
Arrays.sort(dy, Collections.reverseOrder());
System.out.println(dy[0]);
}
static class Brick implements Comparable<Brick>{
public Brick(int s, int h, int w) {
this.s = s;
this.h = h;
this.w = w;
}
int s; //밑면 넓이
int h; //높이
int w; //무게
@Override
public int compareTo(Brick o) {
return o.s - this.s;
}
}
}
実施プロセス全体は従来のLIS問題と同じである.比較条件が違うだけです.順番を守るという説明がなかったので、広いところから、昇順に並べて、それから(この部分とは思わなかったので、何度も編んで、それから間違った答えが出てきました)
にじゅう
下部のレンガは上部のレンガより大きい必要があるため、条件によって更新(更新時に高さ値に更新)されます.
dy降順ソート後最大値出力
Reference
この問題について(いちばん高い塔を建てる), 我々は、より多くの情報をここで見つけました https://velog.io/@yonii/가장-높은-탑-쌓기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol