POJ 1088: Skiing

-

POJ 1088: Skiing

Original Problem Statement

Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
 1  2  3  4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。

Translation

On a 2D array, find the longest sequence of entries such that the sequence satisfies the following:
  • For every entry i in the sequence (excluding the last), the entry after it, j, is less than i.
  • For every entry i in the sequence (excluding the last), it is adjacent to the entry after it, j, on the 2D array.

How You Should Think Of This Problem

Find the longest decreasing subsequence in a 2D array.

How To Solve It

Instead of thinking how to implement LIS for a 2D array, think about how to convert it into a problem already seen before - well, 1D LIS.
Let's store the data in an 1D array and include its row and column to keep where the entry was from.

Then, to make sure requirement #1 is satisfied, we sort the array. The row and column data is still binded to the entries, however!
From here on, requirement #2 is easy to satisfy by checking every single entry pair.
This provides an O(n^4) algorithm, which runs in our time limits.

Code

Memoization (9/10)

#include <algorithm>
#include <iostream>
#include <cmath>
 
using namespace std;
 
int aray[105][105], b[105][105];
int r, c;
bool vist[105][105];
const int vx[] = {1, 0, -1, 0};
const int vy[] = {0, 1, 0, -1};
struct node
{
    int r, c;
};

int LIP(node x)
{
    if(b[x.r][x.c] != -1) return b[x.r][x.c];
    int maxi = 1;
    for(int d=0; d<4; d++)
    {
        int nr = x.r + vx[d];
        int nc = x.c + vy[d];
        if(nr >= 0 && nr < r && nc >= 0 && nc < c && \
           aray[x.r][x.c] > aray[nr][nc]) 
            maxi = max(maxi, LIP({nr, nc}) + 1);
    }
    return b[x.r][x.c] = maxi;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> r >> c;
    for(int i=0; i<r; i++)
        for(int j=0; j<c; j++)
            cin >> aray[i][j];
    int best = 1;
    for(int sr=0; sr<r; sr++)
        for(int sc=0; sc<c; sc++)
        {
            for(int i=0; i<r; i++)
                for(int j=0; j<c; j++)
                    b[i][j] = -1;
            LIP({sr, sc});
            for(int qr=0; qr<r; qr++)
                for(int qc=0; qc<c; qc++)
                    best = max(best, b[qr][qc]);
        }
    cout << best << endl;
}

Tabulation (AC)

#include <algorithm>
#include <iostream>

using namespace std;

struct tile
{
    int h, x, y;
    constexpr bool operator<(const tile other) const
    {
        return h > other.h;
    }
} f[10005];
int b[10005];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int r, c;
    cin >> r >> c;
    for(int i=0; i<r; i++)
        for(int j=0; j<c; j++)
        {
            cin >> f[i*c+j].h;
            f[i*c+j].x = i;
            f[i*c+j].y = j;
        }
    sort(f, f+r*c);
    int best = 0;
    for(int i=r*c-1; i>=0; i--)
    {
        for(int j=i+1; j<r*c; j++)
            if(abs(f[i].x - f[j].x) + abs(f[i].y - f[j].y) == 1 && f[i].h > f[j].h)
                b[i] = max(b[i], b[j] + 1);
        best = max(best, b[i]);
    }
    cout << best + 1 << endl;
}




Comments

Post a Comment

Popular posts from this blog

OpenJudge 1768: Kadane's Algorithm on 2D Arrays

-
OpenJudge 1768: Kadane's Algorithm on 2-D Arrays Simple Version Given a 2-D matrix of integers, find the sub-matrix of this whose sum is maximized, and find that sum. The size of the matrix is no larger than 100 by 100. Analysis O(N^4) - Works, but naive     That's true, an naive O(N^4) version would work. We simply need to calculate (two dimensional!) prefix sums first. A quick review to what 2-D prefix sums are:     The 2-D prefix sum of two coordinates, X and Y, is the sum of all elements that have X-coordinate less than or equal to X, and Y coordinate less than or equal to Y.     It can be calculated through tabulation by removing overlapping areas.     Let P be the prefix sum array and V be the array of values, so the formula is as follows:     P[x, y] = V[x, y] - P[x-1, y] - P[x, y-1] + P[x-1, y-1].     We need to add the P[x-1, y-1] at the end since subtracting P[x-1, y] and P[x, y-1]...
Read more

USACO 2018 Open: Milking Order and Topological Sort

-
USACO 2018 US Open Contest, Gold Problem 2. Milking Order We need to find the biggest number X such that the first X observations are satisfied. Notice that this is perfect to do a binary search on: the invariant is that if the first X observations are satisfied, all observations X-1 will be satisfied; if the first X are insatisfied, all observations X+1 will not be satisfied. So how do we check if all observations to X are satisfied? Let us assemble a graph, in which each observation O_1, O_2, O_3, ... O_i, ... O_l(o) is represented as an edge between O_i and O_i+1 for all i. These observations are satisfiable if and only if this graph has a topological sorting. Lexicographic topological sorting on a graph can be done in O(E + V log_2 V) time (log_2 V because of priority_queue to extract lowest element). So, our total time complexity will be O((E + NlogN) logM). Here, E=200K (the sum of the M_i), N=100K, and M=50K, so it's fast enough. LTS can be easily implemented with ...
Read more