首页 > ACM题库 > HDU-杭电 > HDU 3134-Nested Shrubbery Boxes-背包问题-[解题报告]HOJ
2014
03-03

HDU 3134-Nested Shrubbery Boxes-背包问题-[解题报告]HOJ

Nested Shrubbery Boxes

问题描述 :


Ye Holy Hand Grenades!

After each commission to install a shrubbery, Roger the Shrubber has to transport many empty planting boxes with a drawn cart. In this instance, a planting box is a wooden box with one open side.

Given a set of n planting boxes, compute the largest number of boxes that can be nested. Specifically, report the number of the largest subset of boxes which may be nested such that the smallest box of the subset fits within the second smallest, the second smallest of the subset fits within the third smallest, the third smallest of the subset fits within the fourth smallest, and so forth.

A box i (bi) fits into box j (bj) if there exists some rotation of bi such that each dimension of bi is less than the corresponding dimension of bj. Any box can be rotated to nest inside another box.

输入:

The input will consist of an unspecified number of box sets. Each set will begin with a line containing n, 0<=n<=500, the number of boxes in the set. Each box will be described on its own line by three positive integers representing length, width and height (Each value will not exceed 1000). The first two numbers of each box description will be followed by a space, the letter ‘x‘, and a space. The end of input occurs when n = -1.

输出:

The input will consist of an unspecified number of box sets. Each set will begin with a line containing n, 0<=n<=500, the number of boxes in the set. Each box will be described on its own line by three positive integers representing length, width and height (Each value will not exceed 1000). The first two numbers of each box description will be followed by a space, the letter ‘x‘, and a space. The end of input occurs when n = -1.

样例输入:

5
145 x 472 x 812
827 x 133 x 549
381 x 371 x 900
271 x 389 x 128
718 x 217 x 491
4
432 x 123 x 139
942 x 844 x 783
481 x 487 x 577
677 x 581 x 701
-1

样例输出:

2
4

题目链接:http://acm.hit.edu.cn/hoj/problem/view?id=3134

根据依赖关系可以建立很多颗树,组成一个森林。然后我们增加一个虚拟节点0,使0作为这些子树根节点的父亲。那么这些森林

就组成了一颗以0为根的树。

接下来我们要在树上建立背包方程:

dp[s][i]代表以s为子树的情况花费了i元钱取得的最大重要度。

dp[s][i] = max(dp[s][i],dp[son][k] + dp[s][i-k]),son是s的儿子节点,k需要枚举。这其实是一个值可变的01背包问题,使用状态压缩时,第二维逆序。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iostream>

using namespace std;

#define Maxn 105
#define Maxm 505

struct Edge
{
    int a,b;
}edge[Maxm];

map<string,int> ma;
bool notroot[Maxn];
int first[Maxn];
int next[Maxm];
int total;
int val[Maxn],deg[Maxn];
int dp[Maxn][1005];
int m,n,p;
int num = 0;

void addEdge(int a,int b)
{
    edge[total].a = a,edge[total].b = b;
    next[total] = first[a];
    first[a] = total++;
}

void dfs(int s)
{
    dp[s][val[s]] = deg[s];
    for(int j=first[s];j!=-1;j=next[j])
    {
        int son = edge[j].b;
        dfs(son);
        //这里应该是01背包的第二维逆序
        for(int i=p;i>=val[s];i--)
        {
            //不同于普通的01背包,需要枚举其值
            for(int k=0;k<=i;k++)
            {
                if(dp[s][i-k]!=-1 && dp[son][k]!=-1)
                    dp[s][i] = max(dp[s][i],dp[s][i-k] + dp[son][k]);
            }
        }
    }
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
    #endif
    int temp1,temp2;
    char name[260],name2[260];
    while(scanf(" %d %d %d",&m,&n,&p)!=EOF)
    {
        ma.clear();
        num = 0;
        memset(notroot,false,sizeof(notroot));
        total = 0;
        memset(first,-1,sizeof(first));
        memset(val,0,sizeof(val));
        memset(deg,0,sizeof(deg));
        memset(dp,-1,sizeof(dp));

        for(int i=0;i<m;i++)
        {
            scanf(" %d %d %s",&temp1,&temp2,name);
            if(ma.find(name) == ma.end()) 
            {
                ma[name] = ++num;
                val[num] = temp1,deg[num] = temp2;
            }
        }
        for(int i=0;i<n;i++)
        {
            scanf(" %s %s",name,name2);
            addEdge(ma[name],ma[name2]);
            notroot[ma[name2]] = true;
        }
        for(int i=1;i<=num;i++)
        {
            if(notroot[i] == false)
            {
                addEdge(0,i);
            }
        }
        dfs(0);
        int ans = 0;
        for(int i=0;i<=p;i++)
        {
            ans = max(ans,dp[0][i]);
        }
        printf("%d\n",ans );
    }
    return 0;
}


参考:http://blog.csdn.net/niuox/article/details/10378813


  1. if(j){
    int ans=a ;
    for(int x=j-1;x>=0;x–){
    if(!a ) break;
    ans=min(ans,a );
    sum+=ans;
    }
    }
    求解释,,dp的思路是什么呢?