HDU 1069 Monkey and Banana ——（DP）-白红宇

HDU 1069 Monkey and Banana ——（DP）

阅读量：6173 次

发布时间：2019-06-21

本文共 1636 字，大约阅读时间需要 5 分钟。

　　简单DP。

　　题意：给出若干种长方体，如果摆放时一个长方体的长和宽小于另一个的长宽，那么它可以放在另一个的上面，问最高能放多少高度。每种长方体的个数都是无限的。

　　做法：因为每种个数都是无限，那么每种按照x,y,z分别重新排列可以得到6种长方体。现在用dp[i]表示选到第i个且第i个必须使用的最大高度，那么转移是从1~i-1中的dp中选一个能放在i的前面的最大值放在i的前面，再加上第i个的高，就得到了dp[i]（如果一个都不能放在i的前面，那就只放i即可）。然后最终答案是dp[1]~dp[n]的最大值。

　　注意点是在dp前必须按照（x，y）先排序，这样可以保证第i个能够放在它前面的一定在1~i-1中（后面的一定x或y比它大）。

　　代码如下：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
         5 using namespace std; 6 const int N = 1e7 + 5; 7 const int inf = 0x3f3f3f3f; 8  9 struct node10 {11     int x,y,z;12     bool operator < (const node & temp) const13     {14         return x == temp.x ? y < temp.y : x < temp.x;15     }16 }p[200];17 18 int dp[200];19 20 int main()21 {22     int kase = 1;23     int n;24     while(scanf("%d",&n) == 1 && n)25     {26         for(int i=1;i<=n;i++)27         {28             scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);29             p[i+n] = (node){p[i].x,p[i].z,p[i].y};30             p[i+2*n] = (node){p[i].y,p[i].x,p[i].z};31             p[i+3*n] = (node){p[i].y,p[i].z,p[i].x};32             p[i+4*n] = (node){p[i].z,p[i].x,p[i].y};33             p[i+5*n] = (node){p[i].z,p[i].y,p[i].x};34         }35         sort(p+1,p+1+6*n);36         memset(dp,0,sizeof dp);37         for(int i=1;i<=6*n;i++)38         {39             dp[i] = p[i].z;40             for(int j=1;j
         
           dp[i]) dp[i] = dp[j] + p[i].z;43             }44         }45         printf("Case %d: maximum height = %d\n",kase++,*max_element(dp+1,dp+1+6*n));46     }47 }

　　顺便考虑一个问题，如果要求的是最大能放几个长方体，那就是LIS的问题了。

转载于:https://www.cnblogs.com/zzyDS/p/6396369.html

你可能感兴趣的文章