Problem BlockTower

Link: http://community.topcoder.com/stat?c=problem_statement&pm=12200&rd=15181

Problem Statement

    Josh loves playing with blocks. Currently, he has N blocks, labeled 0 through N-1. The heights of all blocks are positive integers. More precisely, for each i, the height of block i is blockHeights[i]. Josh is interested in making the tallest block tower possible. He likes all his towers to follow three simple rules:

1. The blocks must be stacked in a single column, one atop another. The height of the tower is simply the sum of heights of all its blocks.
2. The labels of blocks used in the tower must increase from the bottom to the top. In other words, whenever Josh places box x on top of box y, we have x > y.
3. Josh will never place a box of an even height on top of a box of an odd height.

You are given the int[] blockHeights. Return the height of the tallest possible block tower Josh can build. 

Definition

    

Class:	BlockTower
Method:	getTallest
Parameters:	int[]
Returns:	int
Method signature:	int getTallest(int[] blockHeights)
(be sure your method is public)

     

Constraints

-blockHeights will contain between 1 and 50 elements, inclusive.-Each element of blockHeights will be between 1 and 50, inclusive. 

Examples

0)    

{4,7}

Returns: 11

The optimal tower contains both blocks. Block 0 is on the bottom of the tower.

1)    

{7,4}

Returns: 7

This time the optimal tower contains just block 0. Josh cannot put block 1 on top of it, because 4 is even and 7 is odd.

2)    

{7}

Returns: 7

3)    

{4}

Returns: 4

4)    

{48,1,50,1,50,1,48}

Returns: 196

Note that in a valid tower the labels of the blocks have to increase from bottom to top. Their heights do not have to. In this case the optimal tower consists of blocks 0, 2, 4, and 6, in this order. Its total height is 48 + 50 + 50 + 48 = 196.

5)    

{49,2,49,2,49}

Returns: 147

6)    

{44,3,44,3,44,47,2,47,2,47,2}

Returns: 273

Solution:

#include<vector>
#include<cstdio>
#include<cstdlib>

using namespace std;

class BlockTower
{
public:
int getTallest(vector<int> blockHeights)
{
int total =  0;
int n = blockHeights.size();
for(int limit = 0; limit <= n; limit++)
{
int ans = 0;
for(int i=0;i<limit;i++)
if(blockHeights[i]%2==0)
ans += blockHeights[i];
for(int i=limit; i<n;i++)
if(blockHeights[i]%2)
ans += blockHeights[i];
total = max(total,ans); 
}
return total;
}
};


Cách 2:
#include<vector>
#include<cstdio>
#include<cstdlib>

using namespace std;

class BlockTower
{
public:
int getTallest(vector<int> blockHeights)
{
int total =  0;
vector<int> old;
vector<int> eve;
int n = blockHeights.size();
old.resize(n,0);
eve.resize(n,0);

if(blockHeights[0]%2)
{
old[0] = blockHeights[0];
}
else
{
eve[0] = blockHeights[0];
}
for(int i=1;i<n;i++)
{
if(blockHeights[i]%2)
{
old[i] += old[i-1] + blockHeights[i];
eve[i] = eve[i-1];
}
else
{
eve[i] = eve[i-1] + blockHeights[i];
old[i] = old[i-1];
}
}
if(blockHeights[0]%2==0)
total = eve[0] + old[n-1];
else
total = old[n-1];

for(int i=1;i<n;i++)
total = max(total,eve[i] + old[n-1] - old[i-1]);
return total;
}
};