【Solution】

接上一篇,在处理有向无环图的最长链问题的时候,可以在做拓扑排序的同时,一边做DP;

设f[i]表示第i个方块作为最上面的最高值;

f[y]=max(f[y],f[x]+h[y]);(x−>y)∈E

这样可以保证,按阶段进行DP,每次在获取f[x]的时候,你可以保证f[x]已经获得了;

最后取max(f[1..n])

【Code】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define Open() freopen("D:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 30;

struct abc{

    LL c,k,g;

};

int n,b[4],nn,du[N*3+100];

LL dp[N*3+100];

abc a[N*3+100];

vector <int> G[N*3+100];

queue <int> dl;

int main()

{

    //Open();

    int kk = 0;

    while (~scanf("%d",&n) && n){

        kk++;

        ms(dp,-1);nn = 0;ms(du,0);

        rep1(i,1,N*3) G[i].clear();

        rep1(i,1,n){

            rep1(j,1,3)

                scanf("%d",&b[j]);

            sort(b+1,b+1+3);

            rep1(j,1,3){

                nn++;

                rep2(k,3,1)

                    if (k!=j){

                        a[nn].c = b[k];

                        break;

                    }

                rep1(k,1,3)

                    if (k!=j){

                        a[nn].k = b[k];

                        break;

                    }

                a[nn].g = b[j];

            }

        }

        n = nn;

        rep1(i,1,n)

            rep1(j,1,n)

                if (a[i].c > a[j].c && a[i].k > a[j].k){

                    G[i].pb(j);

                    du[j]++;

                }

        while (!dl.empty()) dl.pop();

        rep1(i,1,n)

            if (du[i]==0){

                dl.push(i);

                dp[i] = a[i].g;

                du[i] = -1;

            }

        while (!dl.empty()){

            int x = dl.front();

            dl.pop();

            int len = G[x].size();

            rep1(i,0,len-1){

                int y = G[x][i];

                if (dp[y]==-1){

                    dp[y] = dp[x] + a[y].g;

                }else

                    dp[y] = max(dp[y],dp[x]+a[y].g);

                du[y]--;

                if (du[y]==0){

                    dl.push(y);

                    du[y]= -1;

                }

            }

        }

        LL d = 0;

        rep1(i,1,n)

            d = max(d,dp[i]);

        printf("Case %d: maximum height = ",kk);

        printf("%lld\n",d);

    }

    return 0;

}