程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ 1093 Monkey and Banana

ZOJ 1093 Monkey and Banana

編輯:C++入門知識

ZOJ 1093 Monkey and Banana


 

題意:給你n個規格的磚塊,告訴你它的長、寬、高,每種規格的磚都有無數塊,長寬小的磚塊(嚴格小於,不能等於)可以疊在長寬大的磚塊上,問你最多能疊多高。

思路:告訴你一種規格的磚其實給了你三種規格的磚,因為磚是可以翻轉的,長寬高可以變化的;

以長為第一變量,寬為第二變量,從大到小排序,這樣墊在第n塊磚下面的只能從前n-1塊選擇,選擇最大值,累加高度即可。

代碼如下:

 

#include 
#include 
#include 
#include 
const int N = 35;
using namespace std;
int n;
int dp[3*N];

struct node
{
	int x, y, z;
	bool operator< (const node &rhs) const{
		if(x != rhs.x) return x > rhs.x;
		return y > rhs.y;
	}
}block[3*N];

int main()
{
	int cnt = 1;
    while(~scanf(%d, &n))
    {
    	int a, b, c;
    	if(n == 0) break;
        for(int i = 0, x, y, z; i < 3 * n; i ++)
        {
        	scanf(%d%d%d, &x, &y, &z);
        	a = max(max(x, y), z);
        	c = min(min(x, y), z);
        	b = (x + y + z) - (a + c);
        	block[i].x = a, block[i].y = b, block[i].z = c;
        	block[++i].x = a, block[i].y = c, block[i].z = b;
        	block[++i].x = b, block[i].y = c, block[i].z = a;
        }
        sort(block, block + 3 * n);
        int maxn;
        for(int i = 0; i < 3*n; i++)
        {
        	maxn = 0;
        	for(int j = 0; j < i; j++)
        	{
        		if(block[j].x > block[i].x && block[j].y > block[i].y &&  block[j].z > maxn)
        		{
        			maxn = block[j].z;
        		}
        	}
        	block[i].z += maxn;
        }
        maxn = 0;
        for(int i = 0; i < 3*n; i++)
        {
        	if(maxn < block[i].z)
        	{
        		maxn = block[i].z;
        	}
        }
        printf(Case %d: maximum height = %d
, cnt, maxn);
        cnt ++;
    }
    return 0;
}
 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved