专栏首页算法修养HOJ-2056 Bookshelf(线性动态规划)

HOJ-2056 Bookshelf(线性动态规划)

L is a rather sluttish guy. He almost never clean up his surroundings or regulate his personal goods, and often can’t find them at need. What’s worse, due to his power of impact in his dorm, not only is he himself sluttish, but he also spreads the habit of sluttery to his roommates. Even those who were originally pretty well-regulated, such as Song, has been affected by him, and seldom do any cleaning. As a result, L often can’t find his book before class, and thus has to suffer from an out-of-book class, during which he often sleeps and wastes time. After this has happend hundreds of times, L finally made a great effort to decide to tidy up his bookshelf. He collected all his books from everywhere in his dorm —- under the beds, on the windowsill, inside the desks……, put them in a huge box, and began to place the books onto his bookshelf. To make his bookshelf look more smart, L decided to arrange his books such that their height on the bookshelf increases(at least not decrease) from left to right. (i.e.the shortest book is on the left,and as one moves towards the right end of the bookshelf the books’ heights either remain the same as the previous book or increase, until the rightmost book is reached which is the tallest on the shelf). This seems a very easy, albeit time-consuming, task. Unfortunately, L has a strange way of putting his books on the shelf. As he takes a book out of the box, he wants to put it on the shelf without moving any of his other books(he is too lazy to do that), and the books should still be arranged in an acceptable way. For each book, he can either put it on the shelf, or put it aside (i.e.not put it on the shelf): if he puts it aside,then he will never put that book on the shelf. In other words, for every book, L may only put the book on the left side, or on the right side of the bookshelf. He may also throw this book away and not put it on the shelf. Here is an example Suppose L’s box contains 5 books, with the following heights: 2 5 1 3 4 Books are drawn strictly from left to right,then the best number of books that L can fit on the shelf is 4. There are two possible ways of doing this: 2 3 4 5 1 3 4 5 In the first case, L puts the book with height 2 on the left side of the shelf. The book with height 5 goes to the right side. The book with height 1 can’t be placed on the shelf (since it would be shorter than the book with height 2, and so would ruin the arrangement).The book with height 3 goes to the left side,and then the book with height 4 can go either to the left or right side. In the second case, L could put the book with height 2 aside.Then he places the book with height 5 on the right side, the book with height 1 on the left side, the book with height 3 on the left side, and the book with height 4 on either the left or right side. Input Input consists of a series of data sets, followed by a negative integer, which implies the end of input and should not be processed. Each data set begins with a line containing an integer N, denoting the number of books in L’s box. The following line consists of N positive integers denoting the height of each book in the box. The order in which these heights are given is the order in which L takes books from the box. You may assume that 1 ≤ N ≤ 100 and the height of each book will be in the range [1,100]. Output For each data set in the input, output a single line containing the sentence “At most X books can be put onto the bookshelf.”, where X is the maximum number of books L can put onto his bookshelf. Sample Input 5 2 5 1 3 4 8 1 8 3 6 5 4 7 2 -1 Sample Output At most 4 book(s) can be put onto the bookshelf. At most 6 book(s) can be put onto the bookshelf.

我解法是在求给定的序列中最长下降子序列中,还要回朔求倒着的最长下降子序列,再把正着的和倒着的加上一起。举个例子 2 5 1 3 4 正着的下降子序列 5 3,5 4,2 1; 相应的倒着的 3 1,4 3 2,3 2或者3 1,明显5 4和4 3 2 组合最长4是重复的,所以答案就是2+3-1; 这个解法时间是0.03秒,算是效率高的吧 大家注意,n==-1的时候break是错的,n<0才可以,我因为看错题目w了10几发

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>

using namespace std;
int a[105];
int dp[105];
int bp[105];
int s[105];
int tag[105];
int n;
int ans;
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        if(n<0)
            break;
        for(int i=1;i<=n;i++)
        {scanf("%d",&a[i]);s[i]=i;}
        memset(dp,0,sizeof(dp));
        ans=0;
        for(int i=1;i<=n;i++)
        {
            int num=0;
            for(int j=i-1;j>=1;j--)
            {
                if(a[i]<=a[j])
                {
                    if(num<dp[j])
                    {num=dp[j];s[i]=j;}
                }
            }
            dp[i]=num+1;
            memset(tag,0,sizeof(tag));
            int cnt=s[i];
            while(s[cnt]!=cnt)
            {
                tag[cnt]=1;
                cnt=s[cnt];
            }
            tag[cnt]=1;
            memset(bp,0,sizeof(bp));
            int sum=0;
            for(int j=i-1;j>=1;j--)
            {
                if(a[j]>a[i]||tag[j])
                    continue;
                int num=0;
                for(int k=j+1;k<i;k++)
                {
                    if(a[j]<=a[k])
                    num=max(num,bp[k]);
                }
                bp[j]=(num+1);
                sum=max(sum,bp[j]);
            }
            ans=max(ans,dp[i]+sum);
        }
        printf("At most %d book(s) can be put onto the bookshelf.\n",ans);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • POJ-1953 World Cup Noise(线性动规)

    World Cup Noise Time Limit: 1000MS Memory Limit: 30000K Total Submissio...

    ShenduCC
  • CodeForces 665B Shopping

    B. Shopping time limit per test 1 second memory limit per test 256 megabyt...

    ShenduCC
  • ZOJ 3202 Second-price Auction

    Time Limit: 1 Second      Memory Limit: 32768 KB

    ShenduCC
  • Kubernetes GC in v1.3

    本文是对kubernetes GC proposal的解读分析,是对GC in kubernetes v1.3的内部结构剖析,并记录了其中一些关键点,以便日后能...

    Walton
  • TW洞见 | 敏捷回顾7步法

    Paulo和TC一直在收集整理关于敏捷回顾的任何想法和活动。在这篇内容里面,他们分享了7步法来帮助你组织你的下一次回顾。 Agenda structure: 1...

    ThoughtWorks
  • 论综合 | 是什么让一个数字前端实现硅农开始学习Floorplan 的?

    如题,是什么让一个数字前端实现硅农开始学习Floorplan 的?是制造工艺的进步,是实现方法学的被迫更新,是养家糊口生的本能,正可谓:头发落完终不悔,为伊消得...

    老秃胖驴
  • How to find “hidden” remote jobs using Google Search.

    By using a special search operator with Google search, you can find remote jobs ...

    仇诺伊
  • Codeforces 1291 Round #616 (Div. 2) C. Mind Control(超级详细)

    You and your n−1 friends have found an array of integers a1,a2,…,an. You have de...

    风骨散人Chiam
  • CodeForces 665B Shopping

    B. Shopping time limit per test 1 second memory limit per test 256 megabyt...

    ShenduCC
  • 使用SAP Transaction Launcher将ABAP Webdynpro嵌入到WebClient UI中

    THINK twice why you want to include an ABAP webdynpro component into CRM UI, as ...

    Jerry Wang

扫码关注云+社区

领取腾讯云代金券