uva 437 The Tower of Babylon(異なるdp)

2598 ワード

私の考えは劉汝佳先生の考えとは違います.
考え方:1つの立方体を6つの立方体に変えます.つまり、長さも幅も違います.
定義状態:d[i]は、iと表記されたブロックが起点として積み重ねられる最高の高さであり、記憶化探索すればよい.
コード(少し長い)
#include 
#include 
#include 

using namespace std;

struct node
{
    int a,b,c;
}blocks[100];
int cnt,n ;
int per[5];
int v_p[5];
int per_p[5];
int g[200][200];
int d[200];
int kase = 1;
void dfs(int step)

{
    if(step == 3)
    {
        blocks[cnt].a = per[0];
        blocks[cnt].b = per[1];
        blocks[cnt].c = per[2];
        cnt++;
        return ;
    }
    for(int i = 0; i < 3; ++i)
    {
        if(!v_p[i])
        {
            per[step] = per_p[i];
            v_p[i] = 1;
            dfs(step + 1);
            v_p[i] = 0;
        }
    }
}
int dp(int i)

{
    int& ans = d[i];
    if(ans > 0) return ans;
    ans = blocks[i].c ;
    for(int j = 0;j < 6 * n;++j)
        if(g[i][j])
             ans = max(ans,dp(j) + blocks[i].c);
    return ans;
}
int main()

{
    while(~scanf("%d",&n) && n)
    {
        memset(g,0,sizeof(g));
        memset(blocks,0,sizeof(blocks));
        memset(d,0,sizeof(d));
        cnt = 0;
        for(int i = 0; i < n; ++i)
        {
            memset(v_p,0,sizeof(v_p));
            scanf("%d%d%d",&per_p[0],&per_p[1],&per_p[2]);
            dfs(0);
        }
        for(int i = 0; i < 6 * n; ++i)
        {
            for(int j = 0; j < 6 * n; ++j)
            {
                if(i != j)
                {
                    if((blocks[i].a > blocks[j].a && blocks[i].b > blocks[j].b) || (blocks[i].a > blocks[j].b && blocks[i].b > blocks[j].a))
                          g[i][j] = 1;
                    else if((blocks[i].a < blocks[j].a && blocks[i].b < blocks[j].b) || (blocks[i].a > blocks[j].b && blocks[i].b > blocks[j].a))
                        g[j][i] = 1;
                }
            }
        }
        /*for(int i = 0;i < 6 * n;++i)
            printf("%d %d %d
",blocks[i].a,blocks[i].b,blocks[i].c); for(int i = 0;i < 6 * n;++i) { for(int j = 0;j < 6 * n;++j) printf("%d ",g[i][j]); printf("
"); }*/ int ans; for(int i = 0;i < 6 * n;++i) ans = dp(i); for(int i = 0;i < 6 * n;++i) if(ans < d[i]) ans = d[i]; printf("Case %d: maximum height = %d
",kase++,ans); } return 0; }