Monkey and Banana

题目链接
题意：有n种不同类型的砖块，要求上面的砖块的长宽严格小于下面的砖块的长宽，问最多可以有多高。（每种类型的砖块可以有无限个）。刚开始想的时候以为是完全背包模型，题中给的限制也很迷惑，每一种可以无限选择，还有两维的限制，所以我想用f[i][j][k]表示在前i个中选择，第i-1个比第i长宽小的情况。这样很表示起来很复杂，考虑很多的情况。

而且我们可以分析到，实际上背包问题是当前的处理过去之后是不能再回来的，也就是选择过去后就不能再选择，而这个问题实际上是可以回来在选择的。所以背包问题不能解决。我们再看这个题实际上是最长上升子序列的模型，不过转移有两个条件而已。
下面是AC代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=110;
int dp[N];
struct node
{
    
    int a,b,c;
    bool operator <(node &w)
    {
    
        if(a!=w.a) return a<w.a;
        else return b<w.b;
    }
}box[N];
int main()
{
    
    int cou=0;
    int n;
    while(~scanf("%d",&n)&&n)
    {
    
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
    
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            if(a>b) swap(a,b);
            if(a>c) swap(a,c);
            if(b>c) swap(b,c);
            box[++cnt]={
    a,b,c};
            box[++cnt]={
    a,c,b};
            box[++cnt]={
    b,c,a};//这里我们可以题中分析出来同一个最多选三次，所以存三个即可
        }
        sort(box+1,box+1+cnt);//这里贪心就是因为这个题中并没有要求从头开始选的，所以我们尽可能从小的开始选
        //找最长上升子序列
        int res=0;
        for(int i=1;i<=cnt;i++)
        {
    
            dp[i]=box[i].c;
            for(int j=1;j<i;j++)
            {
    
                if(box[i].a>box[j].a&&box[i].b>box[j].b) dp[i]=max(dp[i],dp[j]+box[i].c);
            }
            res=max(res,dp[i]);
        }
        printf("Case %d: maximum height = %d\n",++cou,res);
    }
    return 0;
}

总结：刚开始的时候我就想到了最长上升子序列的模型，但是一看到就以为是二维的直接砍了，根本没有细想实际上是有两个条件，把这个题想复杂了，一直以为是完全背包模型。所以做题再有任何的想法一定要把自己想出的想法认真思考后再定夺，防止一上来就把正确的想法给否了，而且dp问题找到正确的转移方程或是模型后其实是很好表达或理解的。