【线性DP】猴子与香蕉

我就是我 2024-03-26 16:39 70阅读 0赞

**可恶，就差一点就能独立写出这道题了！**

[4548. 猴子和香蕉 - AcWing题库][4548. _ - AcWing]

题意：

![bee1bfbae5e15a76a8968f13222a6741.png][]

思路：

设计状态的时候一开始不知道怎么设，后来试了一下发现这样设很合理

**因此在设状态的时候很多时候都要试一试**

**当时间或空间吃不消时，可以更换定义域和值域，或者直接降维**

**甚至可以直接忽略阶段设状态**

设dp\[i\]表示前i个积木能堆起来的最大高度，然后去转移

当且仅当上一个积木的长和宽都大于这个时转移

要把这些积木排序，按长和宽从大到小排序

if(a[i].x<a[j].x&&a[i].y<a[j].y) dp[i]=max(dp[i],dp[j]+a[i].h);

到目前为止，想的都是对的

但是我却忽略了一个很重要的条件：积木哪个作为高是不确定的

因此，我们还得去枚举哪个是作为高，即相当于把积木数目\*6

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=2e2+10;
    struct ty{
        int x,y,h;
    }a[mxn];
    bool cmp(ty x,ty y){
        if(x.x==y.x) return x.y>y.y;
        return x.x>y.x;
    }
    int n,x,y,h,T=0;
    int dp[mxn];
    void solve(){
        while(cin>>n&&n!=0){
            memset(dp,0,sizeof(dp));
            for(int i=1;i<=n;i++){
                cin>>x>>y>>h;
                a[i].x=x;         a[i].y=y;           a[i].h=h;
                a[i+n].x=x,  a[i+n].y=h,    a[i+n].h=y;
                a[i+2*n].x=y,a[i+2*n].y=x,a[i+2*n].h=h;
                a[i+3*n].x=y,a[i+3*n].y=h,a[i+3*n].h=x;
                a[i+4*n].x=h,a[i+4*n].y=x,a[i+4*n].h=y;
                a[i+5*n].x=h,a[i+5*n].y=y,a[i+5*n].h=x;
            }
            n*=6;
            sort(a+1,a+1+n,cmp);
            int ans=0;
            for(int i=1;i<=n;i++){
                dp[i]=a[i].h;
                for(int j=1;j<i;j++){
                    if(a[i].x<a[j].x&&a[i].y<a[j].y) dp[i]=max(dp[i],dp[j]+a[i].h);
                }
                ans=max(ans,dp[i]);
            }
            cout<<"Case "<<++T<<": maximum height = "<<ans<<'\n';
        }
    }
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[4548. _ - AcWing]: https://www.acwing.com/problem/content/description/4551/
[bee1bfbae5e15a76a8968f13222a6741.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/bab9320a439a4f418734342ce9c31c28.png