욕심법+동태 기획
너무 멋있어요. 예전에 어떻게 풀어야 할지 몰랐던 문제를 오늘 한 번에 제출하고 통과했어요.이것은 나의 노력에 대한 일종의 긍정이다.
이 문제는 욕심법에 동태적인 계획을 더해서 처음에는 길이와 넓이를 앞에 둔 다음에 가장 긴 상승자 서열을 구하는 방법으로 최대치를 구한다고 생각한다
벽돌 한 개를 무한히 쓸 수 있지만, 사실 너는 종류별로 최대 세 번을 쓸 수 있다는 것을 발견할 수 있다.그래서 나는 세 가지 상황을 모두 구조체에 넣고 순서를 정했다.
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define size 200
struct brick{
int l, w, h; // 、 、
}bri[size];
int dp[size];
int index_bri;
int cmp(const brick &a, const brick &b){
if(a.l == b.l){
if(a.w == b.w)
return a.h > b.h; //
return a.w < b.w; //
}
return a.l < b.l; //
}
void init(int l, int w, int h){
bri[index_bri].l = l;
bri[index_bri].w = w;
bri[index_bri++].h = h;
}
int main()
{
//freopen("in.txt", "r", stdin);
int n, i, j, a, b, c, iCase = 0, max;
while(cin>>n && n){
index_bri = 0;
max = 0;
for(i = 0; i < n; i++){
cin>>a>>b>>c;
init(a, b, c); //
init(a, c, b);
init(b, a, c);
init(b, c, a);
init(c, a, b);
init(c, b, a);
}
sort(bri, bri + index_bri, cmp);
for(i = 0; i < index_bri; i++)
dp[i] = bri[i].h;
for(i = 1; i < index_bri; i++){
for(j = 0; j < i; j++){
if(bri[j].l < bri[i].l && bri[j].w < bri[i].w && dp[j] + bri[i].h > dp[i]){
dp[i] = dp[j] + bri[i].h;
if(dp[i] > max)
max = dp[i];
}
}
}
cout<<"Case "<<++iCase<<": maximum height = "<<max<<endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
