精华内容
下载资源
问答
  • 结构体block[i]有五个变量,x,y,z,area,maxh,area为底面面积,maxh为以该方块为最顶层的方块塔的最大高度。 首先将结构体按area排序,其次按x排序。 block[i].maxh = max( block[0~i-1].maxh ) + block...

    原题地址

    Monkey and Banana

    Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
    Total Submission(s): 14290 Accepted Submission(s): 7514


    Problem Description
    A group of researchers are designing an experiment to test the IQ of a monkey. They will hang a banana at the roof of a building, and at the mean time, provide the monkey with some blocks. If the monkey is clever enough, it shall be able to reach the banana by placing one block on the top another to build a tower and climb up to get its favorite food.

    The researchers have n types of blocks, and an unlimited supply of blocks of each type. Each type-i block was a rectangular solid with linear dimensions (xi, yi, zi). A block could be reoriented so that any two of its three dimensions determined the dimensions of the base and the other dimension was the height.

    They want to make sure that the tallest tower possible by stacking blocks can reach the roof. The problem is that, in building a tower, one block could only be placed on top of another block as long as the two base dimensions of the upper block were both strictly smaller than the corresponding base dimensions of the lower block because there has to be some space for the monkey to step on. This meant, for example, that blocks oriented to have equal-sized bases couldn't be stacked.

    Your job is to write a program that determines the height of the tallest tower the monkey can build with a given set of blocks.

    Input
    The input file will contain one or more test cases. The first line of each test case contains an integer n,
    representing the number of different blocks in the following data set. The maximum value for n is 30.
    Each of the next n lines contains three integers representing the values xi, yi and zi.
    Input is terminated by a value of zero (0) for n.

    Output
    For each test case, print one line containing the case number (they are numbered sequentially starting from 1) and the height of the tallest possible tower in the format "Case case: maximum height = height".

    Sample Input
    1 10 20 30 2 6 8 10 5 5 5 7 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 5 31 41 59 26 53 58 97 93 23 84 62 64 33 83 27 0

    Sample Output
    Case 1: maximum height = 40 Case 2: maximum height = 21 Case 3: maximum height = 28 Case 4: maximum height = 342

    题目大意:

    给你n个长方体,并给出长宽高。

    如果下面的长方体的长比上面一个长方体的长要长,宽比上面一个长方体的宽要宽,则它们可以叠在一起。一个长方体可以有无限个。

    每一种长方体都可以有3种摆放姿态,三个面分别作为底面摆放。


    解题思路:

    每个长方体分三种姿势存三次,并且每个长方体的底面的长要比宽大。

    每次读入长宽高的时候,先排序。a>=b>=c

    block[i].x=a;block[i].y=b;block[i].z=c;

    block[i].x=a;block[i].y=c;block[i].z=b;

    block[i].x=b;block[i].y=c;block[i].z=a;


    结构体block[i]有五个变量,x,y,z,area,maxh,area为底面面积,maxh为以该方块为最顶层的方块塔的最大高度。


    首先将结构体按area排序,其次按x排序。

    block[i].maxh = max( block[0~i-1].maxh ) + block[i].z;

    其中,0~i-1 内的方块中,必须满足底面长大于block[i]的底面长,宽大于block[i]的底面宽,才参与比较。



    AC代码:

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    
    struct node
    {
        int x,y,z,maxh,area;
    } nodes[111];
    
    int cmp(node a,node b)
    {
        if(a.area==b.area)
            return a.x>b.x;
        else
            return a.area>b.area;
    }
    
    int edge[5];
    int main()
    {
        int n;
        int cake=1;
        while(~scanf("%d",&n))
        {
            if(n==0) break;
            int p=0;
            for(int i=0; i<n; i++)
            {
                scanf("%d%d%d",&edge[0],&edge[1],&edge[2]);
                sort(edge,edge+3);
                nodes[p].x=edge[2];
                nodes[p].y=edge[1];
                nodes[p].z=edge[0];
                nodes[p].area=nodes[p].x*nodes[p].y;
                p++;
                nodes[p].x=edge[2];
                nodes[p].y=edge[0];
                nodes[p].z=edge[1];
                nodes[p].area=nodes[p].x*nodes[p].y;
                p++;
                nodes[p].x=edge[1];
                nodes[p].y=edge[0];
                nodes[p].z=edge[2];
                nodes[p].area=nodes[p].x*nodes[p].y;
                p++;
    
            }
            sort(nodes,nodes+p,cmp);
    
            nodes[0].maxh=nodes[0].z;
            int ans=0;
            for(int i=0;i<3*n;i++)
            {
                nodes[i].maxh=0;
                for(int j=0;j<i;j++)
                {
                    if(nodes[i].x<nodes[j].x&&nodes[i].y<nodes[j].y)
                    {
                        nodes[i].maxh=max(nodes[i].maxh,nodes[j].maxh);
                    }
                }
                nodes[i].maxh+=nodes[i].z;
                ans=max(nodes[i].maxh,ans);
            }
            printf("Case %d: maximum height = %d\n",cake++,ans);
    
        }
        return 0;
    }
    



    展开全文
  • 最长有序子序列

    千次阅读 2016-07-22 17:44:22
    ACM模版最长有序子序列/* * 递增/递减/非递增/非递减 */ const int N = 1001; int a[N], f[N], d[N]; // d[i]用于记录a[0...i]的最大长度int bsearch(const int *f, int size, const int &a) { int l = 0, r = ...

    ACM模版

    最长有序子序列

    /*
     *  递增(默认)
     *  递减 
     *  非递增
     *  非递减 (1)>= && <  (2)<  (3)>=
     */
    const int MAXN = 1001;
    
    int a[MAXN], f[MAXN], d[MAXN];   //  d[i] 用于记录 a[0...i] 以 a[i] 结尾的最大长度
    
    int bsearch(const int *f, int size, const int &a)
    {
        int l = 0, r = size - 1;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (a > f[mid - 1] && a <= f[mid])  //  (1)
            {
                return mid; 
            }
            else if (a < f[mid])
            {
                r = mid - 1;
            }
            else
            {
                l = mid + 1;
            }
        }
        return -1;
    }
    
    int LIS(const int *a, const int &n)
    {
        int i, j, size = 1;
        f[0] = a[0];
        d[0] = 1;
        for (i = 1; i < n; ++i)
        {
            if (a[i] <= f[0])               //  (2)
            {
                j = 0;
            }
            else if (a[i] > f[size - 1])    //  (3)
            {
                j = size++;
            }
            else
            {
                j = bsearch(f, size, a[i]);
            }
            f[j] = a[i];
            d[i] = j + 1;
        }
        return size;
    }
    
    int main()
    {
        int i, n;
        while (scanf("%d", &n) != EOF)
        {
            for (i = 0; i < n; ++i)
            {
                scanf("%d", &a[i]);
            }
            printf("%d\n", LIS(a, n));      // 求最大递增 / 上升子序列(如果为最大非降子序列,只需把上面的注释部分给与替换)
        }
        return 0;
    }

    2017.4.12 23:59 代码注释修正 以 a[i] 结尾

    展开全文
  • f[]用于记录a[]数组中,以对应位置数据为开头的最长有序序列长度 p[]用于记录a[]数组中,以对应位置数据为开头的前一个数据位置 使用position记录最大长度位置 以a[]={1,4,7,2,5,8,3,6,9},盘算最长递增有...

    新手发帖,很多方面都是刚入门,有错误的地方请大家见谅,欢迎批评指正

        算法原理:

        数组a[]为待处理数组

        f[]用于记录a[]数组中,以对应位置数据为开头的最长有序序列长度

        p[]用于记录a[]数组中,以对应位置数据为开头的前一个数据位置

        使用position记录最大长度位置

        以a[]={1,4,7,2,5,8,3,6,9},盘算最长递增有序子序列为例

        初始化f[]={1, 1, 1, 1, 1, 1, 1,1,1},p[]={0,1,2,3,4,5,6,7,8}

        盘算f[i]时,f[i]=max(f[j]+1) ,(其中,a[i]>a[j],i>j>=0),意思是以a[i]为开头,找出在a[i]前比a[i]小的数据中以该数据为开头的最大有序子序列长度max(f[j]),则以a[i]开头的最大有序子序列长度为max(f[j])+1。盘算同时定义p[i]=j,标记a[i]为开头的最长子序列的前一个数据a[j]的位置。同时判断此时最大长度a[i]是不是比当前最大长度max大,如果a[i]更大则更新position

        a[]={1,4,7,2,5,8,3,6,9}

        i=0   f[]={1,1,1,1,1,1,1,1,1},  p[]={0,1,2,3,4,5,6,7,8}

        i=1   f[]={1,2,1,1,1,1,1,1,1},  p[]={0,0,2,3,4,5,6,7,8}  4>1,所以最大长度为2,position=1

        i=2   f[]={1,2,3,1,1,1,1,1,1},  p[]={0,0,1,3,4,5,6,7,8}  7>4,7>1 其中4开头的长度为2,所以最大长度为3,position=2

        i=3   f[]={1,2,3,2,1,1,1,1,1},  p[]={0,0,1,0,4,5,6,7,8}  2>1 所以最大长度为2

        i=4   f[]={1,2,3,2,3,1,1,1,1},  p[]={0,0,1,0,1,5,6,7,8}  5>1,5>4,5>2,其中以4开头的长度为2,所以最大长度为3

        i=5   f[]={1,2,3,2,3,4,1,1,1},  p[]={0,0,1,0,1,2,6,7,8}  8比前面的数据都大,所以最大长度为4,position=5

        i=6   f[]={1,2,3,2,3,4,3,1,1},  p[]={0,0,1,0,1,2,3,7,8}  3>1,3>2,其中以2开头的长度为2,所以最大长度为3

        每日一道理
    这浓浓的母爱使我深深地认识到:即使你是一只矫健的雄鹰,也永远飞不出母爱的长空;即使你是一条扬帆行驶的快船,也永远驶不出母爱的长河!在人生的路上不管我们已走过多远,还要走多远,我们都要经过母亲精心营造的那座桥!

        i=7   f[]={1,2,3,2,3,4,3,4,1},  p[]={0,0,1,0,1,2,3,4,8}  6>1,6>4,6>2,6>5,6>3,其中以5开头长度为3,所以最大长度为4

        i=8   f[]={1,2,3,2,3,4,3,4,5},  p[]={0,0,1,0,1,2,3,4,5}  9比前面数据都大,所以最大长度为5,position=8

        在对全部a中元素循环当时,通过max记录下最后数据位置,以及p记录的前一个数据的位置,可以递归求出LIS

    #include<stdio.h>
    #include<algorithm>
    using namespace std;
    int f[10001];
    int p[10001];
    struct Mouse
    {
        int w;
        int s;
        int n;
    } M[10001];
    bool compare(const Mouse &a, const Mouse &b)
    {
        if(a.w==b.w)
            return a.s > b.s;
        else
            return a.w < b.w;
    }
    void printLIS(int max_l)
    {
        if(p[max_l]==max_l)
        {
            printf("%d\n",M[max_l].n);
            return;
        }
        printLIS(p[max_l]);
        printf("%d\n",M[max_l].n);
    }
    int main()
    {
        int i=1,max=0,max_l=0;
        while(scanf("%d %d",&M[i].w,&M[i].s)!=EOF)
        {
            f[i]=1;
            p[i]=i;
            M[i].n=i;
            i++;
        }
        sort(M+1,M+i,compare);
        for(int k=1; k<i+1; k++)
        {
            for(int j=1; j<k; j++)
            {
                if(M[j].s>M[k].s&&M[j].w<M[k].w)
                {
                    if((f[j]+1)>f[k])
                    {
                        f[k]=f[j]+1;
                        p[k]=j;
                        if(f[k]>max)
                        {
                            max = f[k];
                            max_l = k;
                        }
                    }
                }
            }
        }
        printf("%d\n",max);
        printLIS(max_l);
        return 0;
    }

        

    文章结束给大家分享下程序员的一些笑话语录: 系统程序员
      1、头皮经常发麻,在看见一个蓝色屏幕的时候比较明显,在屏幕上什幺都看不见的时候尤其明显;
      2、乘电梯的时候总担心死机,并且在墙上找reset键;
      3、指甲特别长,因为按F7到F12比较省力;
      4、只要手里有东西,就不停地按,以为是Alt-F、S;
      5、机箱从来不上盖子,以便判断硬盘是否在转;
      6、经常莫名其妙地跟踪别人,手里不停按F10;
      7、所有的接口都插上了硬盘,因此觉得26个字母不够;
      8、一有空就念叨“下辈子不做程序员了”;
      9、总是觉得9号以后是a号;
      10、不怕病毒,但是很害怕自己的程序;

    --------------------------------- 原创文章 By
    长度和最大
    ---------------------------------

    转载于:https://www.cnblogs.com/jiangu66/archive/2013/05/29/3106624.html

    展开全文
  • 一种长方体有六种摆法,但通过长宽排序后,还有三种摆法,将所有的摆法先按长后按宽从小到大排序,然后就是最长有序子序列的思路了 dp[i]表示前i种摆法的最大高度 AC代码: #include <bits/stdc++.h> using ...

    题目链接: [Monkey and Banana]


    大致题意:

    给你n种长方体,计算最高能堆多高(要求位于上面的长方体的长要大于下面长方体的长,上面长方体的宽大于下面长方体的宽)


    解题思路:

    相当于最长有序子序列

    一种长方体有六种摆法,但通过长宽排序后,还有三种摆法,将所有的摆法先按长后按宽从小到大排序,然后就是最长有序子序列的思路了

    dp[i]表示前i种摆法的最大高度


    AC代码:

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int INF = 0x3f3f3f3f;
    struct node {
    	int l, w, h;
    }a[100];
    int dp[100];
    bool cmp(node p, node q) {
    	if (p.l == q.l)return p.w < q.w;
    	return p.l < q.l;
    }
    int main(void)
    {
    	int t = 1;
    	int n, l, w, h, cnt;
    	while (scanf("%d", &n), n) {
    		cnt = 0;
    		memset(dp, 0, sizeof dp);
    		for (int i = 1; i <= n; ++i) {
    			scanf("%d%d%d", &l, &w, &h);
    			a[cnt].h = l; a[cnt].l = w > h ? w : h; a[cnt++].w = w > h ? h : w;
    			a[cnt].h = w; a[cnt].l = l > h ? l : h; a[cnt++].w = l > h ? h : l;
    			a[cnt].h = h; a[cnt].l = l > w ? l : w; a[cnt++].w = l > w ? w : l;
    
    		}
    		sort(a, a + cnt, cmp);
    		dp[0] = a[0].h;
    		int maxx;
    		for (int i = 1; i < cnt; ++i) {
    			maxx = 0;
    			for (int j = 0; j < i; ++j) {
    				if (a[j].l < a[i].l && a[j].w < a[i].w) maxx = max(maxx, dp[j]);
    			}
    			dp[i] = maxx + a[i].h;
    		}
    		cout << "Case " << t++ << ": maximum height = " << *max_element(dp, dp + cnt) << endl;
    	}
    	return 0;
    }
    

    END

    展开全文
  • hdu1160--最长有序子序列

    千次阅读 2013-05-28 23:34:46
    算法原理: 数组a[]为待处理数组 f[]用于记录a[]数组中,以对应位置数据为结尾的最长有序序列长度...以a[]={1,4,7,2,5,8,3,6,9},计算最长递增有序子序列为例 初始化f[]={1, 1, 1, 1, 1, 1, 1,1,1},p[]={0,1,2,3,4,5,6
  • 方法一:dp,对应原序列的每个元素,dp数组记录包含这个数在内的与之前所有数一起能构成的最长有序子序列的长度,最后对dp数组遍历取最大值即可   #include #include #include #include using namespace std;...
  • //算法8.10 相邻两个有序子序列的归并 #include <stdio.h> #include<stdlib.h> #define MAXSIZE 20 //顺序表的最大长度 typedef struct { int key; char *otherinfo; }RedType; ...
  •  将长方体的6种长款高都提取出来保存到结构体种,按照长度优先相等的按照宽度排序,得到的序列跑一个最长下降子序列就出来了,dp[i]代表第i个塔为最上层塔,当这个塔为止的塔的最大高度。 #include&lt;...
  • 题意:从START跳往END,只能前进不能后退,而且只能跳到比当前点的分数大的点。...运用最长有序子序列的思想,稍稍改动下就可以咯。 #include using namespace std; #define N 1003 int a[N],f[N];
  • 我们将原数组放入一个有序的数组中,如果大于最大元素则加入数组,否则每次二分查找大于等于他的那个数,并替换掉它,这里这个数不代表数的长度,只代表以该数结尾的序列的最大上升子序列的个数为这个数在数组中位置...
  • //求最大子序列的和(有顺序的),区别挤牛奶的无序最大子序列 //如果你画出股票图的话会很好理解 public int maxProfit ( int [] prices) { int finalMax = 0 ; int temp_max = 0 ; for ( int...
  • 题目描述 ...例如,数列(1, 7, 3, 5, 9, 4, 8)的有序上升子序列,像(1, 7), (3, 4, 8)和许多其他的子序列。在所有的子序列中,最长的上升子序列的长度是4,如(1, 3, 5, 8)。 现在你要写一个程序,
  • 书店管理员要把书架上的书整理一下,其实就是一排书,让书的排序是按照书的高低,每本书有一个重量,重量越大,...为什么是2,因为这里只需要把第4,第5本书移动到第三本书的前面,就能够保证书的有序,移动的重量和...
  • 给定一个整数数组 nums ,找出一个序列中乘积最大的连续子序列(该序列至少包含一个数)。 题目分析 这时一个很典型的动态规划题目,数组不一定是有序的,而且连续子序列中的符号也不一定一致,这是两点需要注意的,...
  • 题目大意:让你求出这个串是否是近似有序串,什么叫做近似有序串呢,...如何求最大有序子串呢,就比较一下最长不上升子序列的长度和最长不下降子序列的长度,取最长的即可。 #include&lt;iostream&gt; #...
  • 1 public static int BiSearch(int[] A,int len,int w) ...因为记录数组总是有序的,所以用二分查找很明智。 3 int left=0; 4 int right=len-1;//len是现在数组有几个元素的长度,而不是数组...
  • 最长上升子序列

    2016-10-07 00:43:03
    最长不下降子序列: 普通的动态规划就是以f[i]表示第I个作为序列尾数的最长序列长度。...改进算法就是把无序变成有序的,建一个数组A,使得A[len]=a[j],表示长度为len的上升子序列的最小末尾数。由于一旦l
  • 最长递增子序列

    2016-08-01 10:00:19
    最朴素的思想:求出以数组中每一个位置结尾的的最长递增子序列,选择其中的最大值,时间复杂度为O(n*n)。 现在有一种更巧妙的思想可以将时间复杂度变为O(n*logn),一看到logn我们很容易想到二分,使用二分的前提条件...
  •  神灯中冒出了灯神,灯神说道:“我将给你一个有序的数列,你可以在保证原有顺序不变的前提下,挑出任意多的数。如果你挑出的数字是严格升序的,那么这段数字的个数就是你女朋友的个数。”  “妈的智障。”鹏神骂...
  • 基本概念从给定的有序序列a[1],a[2],…,a[n]中选取b[1],b[2],…,b[m],其中b[1][2] [m],且选出的子序列中在原序列的先后顺序不变。求一种令m最大的取法。即最长上升子序列问题(Longest increasing subsequence) ...
  • 给定字符串S和T,在S中寻找最小连续子串W,使得T是W的子序列有序)。如果没有找到返回"",如果找到多个最小长度的子串,返回左 index 最小的。 https://blog.csdn.net/weixin_45588823/article/details/100642933...
  • 最长公共子序列算法应用非常广泛:比如染色体中DNA片段的的研究,基于最长公共子序列的微博谣言溯源研究等等。所以掌握与应用该基础算法是...必要条件(1):子序列必须是有序的; (2) : 子序列的长度最大; 注意...
  • 最长递增子序列,传统方法用dp思想,状态转移方程如下:  dp[i] = Max{dp[j] | j 传统写法是求dp[i]时枚举所有小于i的j,然后...maxV[i] 代表长度为i的递增子序列最大元素的最小值。 我们会发现该数组是有序的,
  • 模拟赛T2 SORT题意转化为:给一个有序数列中的逆序对之间连边,求最大独立集...若不选最长上升子序列中的数作为最大独立集,那么答案只会不变或更劣。所以答案就是最长上升子序列长度。随便用什么求都可以了。...
  • 最长递增子序列 O(NlogN)算法

    千次阅读 2014-03-06 07:35:27
    今天学习了求最长递增子序列这个题的O(NlogN...同时还需要一个变量len,用来记录当前所遇到的所有元素能组成的递增子序列最大长度。分析后可以发现,DP这个数组一定是有序的,所以每次对它的更新,可以用二分法来实现
  • 设f表示以一个位置结尾的最长上升子序列长度。 注意插入的数大小有序,也就是只需要知道每次插入数左边所有位置的f最大值就可以得到它的f。 因为要支持插入操作,用treap/splay维护序列即可 代码 #include<bits/...
  • 最长递增子序列优化算法(时间复杂度为nlgn) // 最长递增子序列优化算法.cpp : Defines the entry point for the console application. //对于j位置的字符,我们需要寻找此位置之前的最大的len[i](i //如果len[i]有序...

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 261
精华内容 104
关键字:

最大有序子序列