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;
}