hdu 1069 Monkey and Banana (dp)

hdu 1069 Monkey and Banana (dp)

//把給定的長方體（不限）疊加在一起，疊加的條件是，上面一個長方體的長和寬都比下面長方體的長
/*
分析：因為每塊積木最多有3個不同的底面和高度，因此先把每塊積木看成三種不同的積木，
每種積木只有一個底面和一個高度。n中類型的積木轉化為3*n個不同的積木的疊加，
對這3 * n個積木的長邊從大到小排序；接下來的問題就是找到一個遞減的子序列，
使得子序列的高度和最大即可。
數組dp：dp[i]表示是以第i塊積木為頂的塔的最大高度
因此可得狀態轉移方程：dp[i] = max(dp[i]，dp[j] + r[i].z)（滿足積木j的底面長和寬都大於積木i的長和寬）
和寬短；求這些長方體能疊加的最高的高度.
*/
# include 
# include 
# include 
using namespace std;
struct node
{
    int x;
    int y;
    int z;
};
struct node r[100010];
bool cmp(node a1,node a2)
{
    if(a1.x!=a2.x)
        return a1.x>a2.x;
    return a1.y>a2.y;
}
int main()
{
    int cas=0;
    int i,j,n,a,b,c,maxh;
    int dp[100010];
    while(~scanf("%d",&n),n)
    {
        for(i=0,j=0; i=0; j--)
            {
                if(r[j].x>r[i].x&&r[j].y>r[i].y)
                {
                    if(dp[j]+r[i].z>dp[i])
                        dp[i]=dp[j]+r[i].z;
                }

            }
            if(maxh