基础DP（最长递减序列变形+判断）

https://vjudge.net/contest/409169#problem/C

题意：给你N个长方体的长a宽b高c，每一个型号的长方体可以用无限多个。用这些长方体来堆一个高度最高的塔，每一个长方体的长和宽必须严格大于上面一个长方体   的长和宽。

题解：

面积排序（如果面积不等则取面积较大的那个，面积相等取高度大的那个）之后，需要找的是最大递减序列（加上长宽的判断）

面积排序之后因为有面积相等的情况所以才要动态规划（取舍），不能全部都加上

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
    int s;//面积
    int upl;//长
    int upr;//宽
    int h;//高
}a[100];
int dp[100];
bool cmp(node x,node y)
{
    if(x.s!=y.s)
        return x.s>y.s;
    else
        return x.h>y.h;
}
int main()
{
    int n;
    int t=1;
    int x,y,z;
    while(cin>>n&&n)
    {
        memset(dp,0,sizeof(dp));
        int k=0;
        for(int i=1;i<=n;i++)
        {
            cin>>x>>y>>z;
            //以x,y为底面
            a[k].s=x*y;
            a[k].upl=x>y?x:y;
            a[k].upr=x>y?y:x;
            a[k++].h=z;
            //以x,z为底面
            a[k].s=x*z;
            a[k].upl=x>z?x:z;
            a[k].upr=x>z?z:x;
            a[k++].h=y;
             //以y,z为底面
            a[k].s=y*z;
            a[k].upl=y>z?y:z;
            a[k].upr=y>z?z:y;
            a[k++].h=x;
        }
        int ans=INT_MIN;
        sort(a,a+k,cmp);
        for(int i=0;i<k;i++)
        {
            dp[i]=a[i].h;
            for(int j=0;j<i;j++)
            {
                if(a[i].s<a[j].s&&a[i].upl<a[j].upl&&a[i].upr<a[j].upr)
                {
                    dp[i]=max(dp[i],dp[j]+a[i].h);
                }
            }
            ans=max(ans,dp[i]);
        }

        printf("Case %d: maximum height = ",t++);
        cout<<ans<<endl;
    }
}

基础DP（最长递减序列变形+判断）

原文：https://www.cnblogs.com/jutian/p/14245498.html