当前位置：首页 > news >正文

UVA437 The Tower of Babylon（记忆化搜索）

news 来源：原创 2024/5/20 23:57:32

传送门

首先一种立方体相当于三种底面不同的立方体，不难发现这里只有底面尺寸能影响到决策，每次输入一个立方体就存三种立方体，因此本题相当于前面嵌套矩形模板的裸题

仍是考虑逆序递推，使用一元组dp[i]记录从序号为i的立方体开始能向下不断叠加的最大高度，那么使用DAG的记忆化搜索模板，对每个立方体搜索，取答案中最大的即可

这种DAG的dp貌似写不了递推，因为感觉递推的话每次考虑叠加的应该是满足的底面尽量小的立方体，也许需要排序？我没有尝试

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;
struct node{
    int x,y,h;
}a[105];

int n,m;
int dp[105],G[105][105];

int solve(int i){
    int& ans=dp[i];
    if(ans>0) return ans;
    ans=a[i].h;
    for(int j=0;j<m;j++)
        if(G[i][j]) ans=max(ans,solve(j)+a[i].h);
    return ans;
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int kase=0;
    while(cin>>n && n){
        m=0;
        for(int i=1,x,y,z;i<=n;i++){
            cin>>x>>y>>z;
            a[m].x=min(y,z);
            a[m].y=max(y,z);
            a[m++].h=x;
            a[m].x=min(x,z);
            a[m].y=max(x,z);
            a[m++].h=y;
            a[m].x=min(x,y);
            a[m].y=max(x,y);
            a[m++].h=z;
        }
        memset(G,0,sizeof G);
        memset(dp,0,sizeof dp); //初始化为0
        for(int i=0;i<m;i++){
            for(int j=0;j<m;j++){
                if(a[i].x<a[j].x && a[i].y<a[j].y)
                    G[i][j]=1;  //G[i][j]代表第i个立方体下可以叠第j个
            }
        }
        int ans=0;
        for(int i=0;i<m;i++)
            ans=max(ans,solve(i));
        cout<<"Case "<<++kase<<": maximum height = "<<ans<<endl;

    }
    return 0;
}