online advertising

Thursday, November 6, 2014

UVa Problem 231 - Testing the CATCHER

Problem:

Please find the problem here.

Solution:

Competitive Programming is right - this is just straightforward application of the longest increasing sub-sequence algorithm.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=167

#include "UVa231.h"

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int UVa231()
{
    int c = 0;
    while (true)
    {
        c++;
        vector<int> missile_heights;
        while (true)
        {
            int missile_height;
            cin >> missile_height;
            if (missile_height == -1)
            {
                break;
            }

            missile_heights.push_back(missile_height);
        }

        if (missile_heights.size() == 0)
        {
            break;
        }

        // represents the longest_decreasing_sequence_length that ends at the index
        vector<int> longest_decreasing_sequence_lengths;
        longest_decreasing_sequence_lengths.push_back(1);

        // represents the longest_decreasing_sequence_length that ends at any index
        int the_longest_decreasing_sequence_length = 1;

        for (unsigned int i = 1; i < missile_heights.size(); i++)
        {
            int longest_decreasing_sequence_length = 1;
            for (unsigned int j = 0; j < i; j++)
            {
                if (missile_heights[j] >= missile_heights[i])
                {
                    longest_decreasing_sequence_length = max(longest_decreasing_sequence_length, longest_decreasing_sequence_lengths[j] + 1);
                }
            }

            longest_decreasing_sequence_lengths.push_back(longest_decreasing_sequence_length);
            the_longest_decreasing_sequence_length = max(the_longest_decreasing_sequence_length, longest_decreasing_sequence_length);
        }

        if (c != 1)
        {
            cout << endl;
        }

        cout << "Test #" << c << ":" << endl;
        cout << "  maximum possible interceptions : " << the_longest_decreasing_sequence_length << endl;
    }
   return 0;
}

No comments :

Post a Comment