자서동규 예제 9-2 UVA - 437 The Tower of Babylon dp
제목 링크:
https://vjudge.net/problem/UVA-437
제목:
문제 풀이:
pp[i][j]: = 이전 i개의 입방체를 고려하고 i개의 입방체는 j가 높은 최대치로 표시됩니다
코드:
1 #include
2 using namespace std;
3 typedef long long ll;
4 #define MS(a) memset(a,0,sizeof(a))
5 #define MP make_pair
6 #define PB push_back
7 const int INF = 0x3f3f3f3f;
8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
9 inline ll read(){
10 ll x=0,f=1;char ch=getchar();
11 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13 return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 1e5+10;
17
18 int n;
19 int block[40][3],d[40][3];
20
21 void get(int* v,int b,int x){
22 int idx = 0;
23 for(int i=0; i<3; i++)
24 if(i!=x)
25 v[idx++] = block[b][i];
26 }
27
28 int dp(int i,int j){
29 if(d[i][j] >= 0) return d[i][j];
30 d[i][j] = 0;
31 int v[2],v2[2];
32 get(v,i,j);
33 for(int a=0; a){
34 for(int b=0; b<3; b++){
35 get(v2,a,b);
36 if(v[0]>v2[0] && v[1]>v2[1])
37 d[i][j] = max(d[i][j],dp(a,b));
38 }
39 }
40 d[i][j] += block[i][j];
41 return d[i][j];
42 }
43
44 int main(){
45 int cas = 0;
46 while(scanf("%d",&n) && n){
47 for(int i=0; i){
48 scanf("%d%d%d",&block[i][0],&block[i][1],&block[i][2]);
49 sort(block[i],block[i]+3);
50 }
51
52 int ans = -INF;
53 memset(d,-1,sizeof(d));
54 for(int i=0; i)
55 for(int j=0; j<3; j++)
56 ans = max(ans,dp(i,j));
57 printf("Case %d: maximum height = %d
",++cas,ans);
58 }
59
60 return 0;
61 }
전재 대상:https://www.cnblogs.com/yxg123123/p/6827594.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.