程序師世界是廣大編程愛好者互助、分享、學習的平台，程序師世界有你更精彩！
設為首頁 加入收藏
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU1069(最長單調遞減數列)

HDU1069(最長單調遞減數列)

編輯：C++入門知識

告訴你n種規模的長方體的長，寬，高，每種規模的長方體個數不限，問你最多能搭多高的塔，塔是由這些長方體搭的，自上而下，每一塊長方體都要比在它下面的長方體的規模小，即長和寬都比下面的長方體要小。注意長方體是可以調整的。

就是按照長和寬來排序，找最長的單調遞減的數列。我們用dp[i]來表示搭建到第i塊長方體的時候塔的最高高度，那麼狀態轉移方程就是dp[i]=max(dp[i],dp[j]+s[i].h)；

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define M 100000+5
#define LL long long
#define Ld __int64
#define eps 0.00001
#define INF 999999999
#define MOD 112233
#define MAX 26
#define PI acos(-1.0)
using namespace std;

struct solid
{
	int l,w,h;
}s[155];

bool cmp(solid a,solid b)
{
	if(a.l==b.l)
	{
		if(a.w==b.w)
			return a.h>b.h;
		return a.w>b.w;
	}
	return a.l>b.l;
}

int main()
{
	int n,cont=1;
	int d[3];
	int dp[155];
	while(~scanf("%d",&n),n)
	{
		int k=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d%d",&d[0],&d[1],&d[2]);
			sort(d,d+3);
			s[k].l=d[2],s[k].w=d[1],s[k++].h=d[0];		//各種長方體
			s[k].l=d[2],s[k].w=d[0],s[k++].h=d[1];
			s[k].l=d[1],s[k].w=d[0],s[k++].h=d[2];
		}
		sort(s,s+k,cmp);
		for(int i=0;i=0;i--)
		{
			for(int j=i+1;js[j].l && s[i].w>s[j].w)
				{
					dp[i]=max(dp[i],dp[j]+s[i].h);
				}
			}
		}
		int ans=-1;
		for(int i=0;i
  1. 上一頁:
  2. 下一頁:
C++入門知識
三月二十一號隨堂小測試（第四周），二十一號第四周

三月二十一號隨堂小測試（第四周），二十一號第四周問題：單元測
UVA10382 Watering Grass

Problem E Watering Grass I
windows下的C++ socket服務器（2）

make_server_socket( port);

poj 2570 Fiber Network （Floyd）

poj 2570 Fiber Network （Floyd）
C++筆試易錯題集（持續更新），筆試錯題集

C++筆試易錯題集（持續更新），筆試錯題集1.如下代碼輸出結
For循環語句的使用，For循環語句使用

For循環語句的使用，For循環語句使用一、For循環語句

相關文章
閱讀排行榜
3Sum Closest 486E - LIS of Sequence(LIS) hdu 4127 Flood-it! (IDA+bfs) HDU 2110-Crisis of HDU(母函數) uva 10069 Distinct Subsequences(高精度 + DP求解子串個數） C++在數組元素個數未知情況下聲明數組，數組聲明 VS2010 c++ 錯誤的處理 什麼是C++中標准輸入？ HOJ_2430 Counting the algorithms SGU 319 Kalevich Strikes Back(線段樹掃描線) UVALive - 2031 Dance Dance Revolution 三維dp
熱門圖文
C++ 讀取配置文件 UTF-8 Unicode Ansi 漢字GB2321幾種編碼轉換程序 php9個超全局變量的用法詳解（一） hdu 5256 序列變換 (LIS變形) 表達式-link環境下為什麼arr.Aggregate(1, (a, b) => a*b)的a 支持換膚功能的窗口實例 C++11 Lambda表達匯總總結 網頁提取-c#如何提取提取淘寶或者京東的一些產品信息
欄目導航
C++基礎知識C++入門知識關於C++
Copyright © 程式師世界 All Rights Reserved