HDU 1069 Monkey and Banana(최대 증가 하위 문자열)
4110 단어 dp
제목의 뜻
주어진 상자의 종류 수량 n, 그리고 대응하는 길이와 너비, 각 상자의 수량은 무한하며, 접을 수 있는 최대 높이는 얼마인지(위 상자의 길이와 너비는 아래 상자보다 엄격히 작다)
사고의 방향
상자마다 세 가지 방치 방식이 있고 수량이 무한하기 때문에 상자마다 세 개의 상자로 볼 수 있다.모든 상자를 주 길이와 부 너비에 따라 선대후소 순서를 정하면 문제는 최대 점증자열을 구하는 것이다.n의 범위가 매우 작기 때문에 30만 있기 때문에 직접 이중 순환 dp로 하면 된다
코드
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;
const int N = 39;
struct Node
{
int a, b, c;
bool operator < (const Node &t) const
{
if(a == t.a)
return b > t.b;
return a > t.a;
}
}node[N*3];
int dp[N*3];
void add(int i, int a, int b, int c)
{
node[i].a = a;
node[i].b = b;
node[i].c = c;
}
int main()
{
int n, T = 1;
while(~scanf("%d", &n) && n)
{
for(int i=0; i<n; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(i*3, max(a, b), min(a, b), c);
add(i*3+1, max(a, c), min(a, c), b);
add(i*3+2, max(c, b), min(c, b), a);
}
sort(node, node+n*3);
dp[0] = node[0].c;
int ans = dp[0];
for(int i=1; i<3*n; i++)
{
int temp = 0;
dp[i] = node[i].c;
for(int j=0; j<i; j++)
{
if(node[i].a<node[j].a && node[i].b<node[j].b)
temp = max(temp, dp[j]);
}
dp[i] += temp;
ans = max(ans, dp[i]);
}
printf("Case %d: maximum height = %d
", T++, ans);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
