Shelving Books | LightOJ

You are a librarian. You keep the books in a well organized form such that it becomes simpler for you to find a book and even they look better in the shelves.

One day you get n new books from one of the library sponsors. And unfortunately they are coming to visit the library, and of course they want to see their books in the shelves. So, you don't have enough time to shelve them all in the shelf in an organized manner since the heights of the books may not be same. But it's the question of your reputation, that's why you have planned to shelve them using the following idea:

You will take one book from the n books from left.
You have exactly one shelf to organize these books, so you may either put this book in the left side of the shelf, right side of the shelf or you may not put it in the shelf. There can already be books in the left or right side. In such case, you put the book with that book, but you don't move the book you put previously.
Your target is to put the books in the shelf such that from left to right they are sorted in non-descending order.
Your target is to put as many books in the shelf as you can.

You can assume that the shelf is wide enough to contain all the books. For example, you have 5 books and the heights of the books are {3, 9, 1, 5, 8} (from left). In the shelf you can put at most 4 books. You can shelve {3, 5, 8, 9}, because at first you got the book with height 3, you stored it in the left side of the shelf, then you got 9 and you put it in the right side of the shelf, then you got 1 and you ignored it, you got 5 you put it in the left with 3. Then you got 5 and you put it in left or right. You can also shelve {1, 5, 8, 9} maintaining the restrictions.

Now given the heights of the books, your task is to find the maximum number of books you can shelve maintaining the above restrictions.

Input

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 100). Next line contains n space separated integers from [1, 10⁵]. The i^th integer denotes the height of the i^th book from left.

Output

For each case, print the case number and the maximum number of books that can be shelved.

Sample

Sample Input	Sample Output
Click to copy 2 5 3 9 1 5 8 8 121 710 312 611 599 400 689 611	Click to copy Case 1: 4 Case 2: 6

LOJ-1283-Shelving Books

The problem asks us to put as many books as possible according to their height in non-descending order from n books. We have to consider the books one by one from left to right. We may skip one or more books. And if the height of a book is greater than or equal than the last added book to the left and less than or equal to the last added book to the right, we can include the book in the shelf. For including the book, we have two options: add the book to the left or add it to the right. We use Dynamic Programming to find the best result.

The statement for the problem says that the height of the books can be in range [1,10⁵]. As 1 <=n <= 100, we can notice that there can be at most 100 distinct heights of the books. So, we can map the heights according to their magnitude. Then all the mapped heights will be within the range [1,100]. Now, our function for DP can have 3 states. One state is for the index of the books. One state is for the height of the last added book to the left and another state is for the height of the last added book to the right. For each book, can skip the book or if the book fulfils the condition, then we can add the book to the left or to the right.

C++ code

#include "bits/stdc++.h"

using namespace std;
using ll = long long;

int book[100], hashed_book[100], n, memo[100][101][102];
map<int,int> rec;
set<int> con;

int dp(int i,int a,int b){
    if(i == n) return 0;
    if(memo[i][a][b] == -1){
        int ans = dp(i+1,a,b);        // skipping the current book. 
        if(hashed_book[i] >= a && b >= hashed_book[i]){
            ans = max(ans,max(dp(i+1,hashed_book[i],b),dp(i+1,a,hashed_book[i]))+1); 
            //including the current book.
        }
        memo[i][a][b] = ans;
    }
    return memo[i][a][b];
}

int main(){  
    int T,s; cin>>T;
    for(int t = 1; t <= T; t++){
        cin>>n;
        s = 0;
        rec.clear(); con.clear();
        for(int i = 0; i < n; i++){
            cin>>book[i];
            con.insert(book[i]);                    // saving the heights in a set to find the distinct heights. 
        }
        for(int r: con) if(!rec.count(r)) rec[r] = ++s;    // mapping the heights.
        for(int i = 0; i < n; i++) hashed_book[i] = rec[book[i]];   // creating a new array with the mapped heights. 
        memset(memo,-1,sizeof(memo));
        ll ans = dp(0,0,101);
        cout<<"Case "<<t<<": "<<ans<<"\n";
    }
    return 0;
}

Note: For the base case, 0 and 101 are used as the last added height of the book to the left and to the right, as a result any height within the range [1,100] will be considered valid.

Tutorial source

Input

Output

Sample

Total Submissions

Users Tried

Users Solved

LOJ-1283-Shelving Books

C++ code