DGA上的动态规划

前言：之前都没有写过建模成有向图来动态规划的，但是这个题可以抽象成有向图来做

我们可以用方块的编号和高来确定底下的长和宽
其实这题说白了就是一个记忆化搜索，但是不知道能不能建模出来而已

在这里插入图片描述

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;int n;
const int N = 35;
struct node{int a[3];
}sto[N];
int dp[N][3];
// 用 dp[i][j] 表示底下是第 i 块方块且采用第j种方式放置的最佳长度int dfs(int i,int j){if(dp[i][j]>0) return dp[i][j];int chang , kuan;if(j==0){dp[i][j] += sto[i].a[0];chang = sto[i].a[1]; kuan = sto[i].a[2];}else if(j==1){dp[i][j] += sto[i].a[1];chang = sto[i].a[0]; kuan = sto[i].a[2];		}else{dp[i][j] += sto[i].a[2];chang = sto[i].a[0]; kuan = sto[i].a[1];}int t = 0;for(int k = 1; k <= n ; k++){for(int q=0;q<3;q++){if(chang<sto[k].a[(q+1)%3] && kuan<sto[k].a[(q+2)%3]){t = max(t,dfs(k,q));}else if(chang<sto[k].a[(q+2)%3] && kuan<sto[k].a[(q+1)%3]){t = max(t,dfs(k,q));}}}dp[i][j] += t;return dp[i][j];
} int main(){int cnt = 0;while(true){cnt ++;cin >> n;if(n==0) break;for(int i=1;i<=n;i++){for(int j=0;j<=2;j++){cin >> sto[i].a[j]; dp[i][j] = 0;}}int ans = 0;for(int i=1;i<=n;i++){for(int j=0;j<=2;j++){ans = max(ans,dfs(i,j));}}cout << "Case " << cnt <<  ": maximum height = " << ans << endl;}return 0;
}