题目链接：点击打开链接
DAG上最长路、
题意：给出n种长方体，（每种无限），要求能摞的最大高度。连边是大的连小的。
#include #include #include #include #include #include #include #include #include #include #include #include #include #define maxn 10000002 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 10000007 #define pp pair #define ull unsigned long long using namespace std; int n,m,dp[110],x[110],y[110],z[110]; bool ma[110][110]; void input() { m=n*3; for(int i=1;i<=m-2;i+=3){ scanf("%d %d %d",x+i,y+i,z+i); x[i+1]=y[i];y[i+1]=z[i];z[i+1]=x[i]; x[i+2]=y[i+1];y[i+2]=z[i+1];z[i+2]=x[i+1]; } } void build() { memset(ma,0,sizeof(ma)); memset(dp,0,sizeof(dp)); for(int i=1;i<=m;i++) for(int j=i+1;j<=m;j++){ if((x[i]>x[j]&&y[i]>y[j])||(x[i]>y[j]&&y[i]>x[j])) ma[i][j]=1; else if((x[j]>x[i]&&y[j]>y[i])||(x[j]>y[i]&&y[j]>x[i])) ma[j][i]=1; } } int dfs(int x) { int& ans=dp[x]; if(ans)return ans; ans=z[x]; for(int i=1;i<=m;i++){ if(ma[x][i])ans=max(ans,dfs(i)+z[x]); } return ans; } int main() { int cas=1; while(scanf("%d",&n)&&n){ input(); build(); int ans=-INF; for(int i=1;i<=m;i++) ans=max(ans,dfs(i)); printf("Case %d: maximum height = %d\n",cas++,ans); } return 0; }