C - Monkey and Banana HDU - 1069——基础dp

Myth丶恋晨 2022-06-10 01:20 168阅读 0赞

Think:  
1知识点：基础dp  
2题意：询问n种箱子在满足  
1>可以不同面为底  
2>一个叠一个  
3>叠的箱子中上面的箱子长和宽都分别严格小于下面的箱子的长和宽  
4>无限个箱子  
条件下能够叠的最高高度

[vjudge题目链接][vjudge]

以下为Accepted代码——基础dp

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    struct Node{
        int x, y, z;
        int w;
        bool operator < (const Node &b) const{
            return w < b.w;
        }
    }link[114];
    
    int tp, dp[114];
    /*dp[i]:表示前i个状态的最高高度*/
    
    int main(){
        int k = 1, n, i, j, x, y, z, ans, mv;
        while(scanf("%d", &n) && n){
            tp = 0;
            for(i = 1; i <= n; i++){
                scanf("%d %d %d", &x, &y, &z);
                link[tp].x = x, link[tp].y = y, link[tp].z = z, link[tp].w = max(x, y), tp++;
                link[tp].x = x, link[tp].y = z, link[tp].z = y, link[tp].w = max(x, z), tp++;
                link[tp].x = y, link[tp].y = z, link[tp].z = x, link[tp].w = max(y, z), tp++;
            }
            sort(link, link+tp);
            for(i = 0; i < tp; i++)
                dp[i] = link[i].z;
            ans = 0;
            for(i = 1; i < tp; i++){
                mv = 0;
                for(j = i-1; j >= 0; j--){
                    if((link[i].x > link[j].x && link[i].y > link[j].y) || (link[i].x > link[j].y && link[i].y > link[j].x)){
                        if(mv < dp[j])
                            mv = dp[j];
                    }
                }
                dp[i] += mv;
                ans = max(ans, dp[i]);
            }
            printf("Case %d: maximum height = %d\n", k++, ans);
        }
        return 0;
    }

[vjudge]: https://vjudge.net/contest/163018#problem/C