首页 > 专题系列 > Java解POJ > POJ 3658 Artificial Lake [解题报告] Java
2013
11-13

POJ 3658 Artificial Lake [解题报告] Java

Artificial Lake

问题描述 :

The oppressively hot summer days have raised the cows’ clamoring to its highest level. Farmer John has finally decided to build an artificial lake. For his engineering studies, he is modeling the lake as a two-dimensional landscape consisting of a contiguous sequence of N soon-to-be-submerged levels (1 ≤ N ≤ 100,000) conveniently numbered 1..N from left to right.

Each level i is described by two integers, its width Wi (1 ≤ Wi ≤ 1,000) and height (like a relative elevation) Hi (1 ≤ Hi ≤ 1,000,000). The heights of FJ’s levels are unique. An infinitely tall barrier encloses the lake’s model on the left and right. One example lake profile is shown below.

            

* * :
* * :
* * 8
* *** * 7
* *** * 6
* *** * 5
* ********** 4 <- height
* ********** 3
*************** 2
*************** 1
Level | 1 |2| 3 |

In FJ’s model, he starts filling his lake at sunrise by flowing water into the bottom of the lowest elevation at a rate of 1 square unit of water per minute. The water falls directly downward until it hits something, and then it flows and spreads as room-temperature water always does. As in all good models, assume that falling and flowing happen instantly. Determine the time at which each elevation’s becomes submerged by a single unit of water.


WATER WATER OVERFLOWS
| |
* | * * | * * *
* V * * V * * *
* * * .... * *~~~~~~~~~~~~*
* ** * *~~~~** : * *~~~~**~~~~~~*
* ** * *~~~~** : * *~~~~**~~~~~~*
* ** * *~~~~**~~~~~~* *~~~~**~~~~~~*
* ********* *~~~~********* *~~~~*********
*~~~~********* *~~~~********* *~~~~*********
************** ************** **************
************** ************** **************

After 4 mins After 26 mins After 50 mins
Lvl 1 submerged Lvl 3 submerged Lvl 2 submerged

Warning: The answer will not always fit in 32 bits.

输入:

* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 describes level i with two space-separated integers: Wi and Hi

输出:

* Lines 1..N: Line i contains a single integer that is the number of minutes that since sunrise when level #i is covered by water of height 1.

样例输入:

3
4 2
2 7
6 4

样例输出:

4
50
26

解题代码:

//* @author 
/**
 * @version 2009/08/21
 * @author sbzlyessit
 */

import java.io.*;
import java.util.*;

public class Main {

    private static final int        MAX_N = 100000;

    private static BufferedReader   in =new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer  st;
    private static int[]            height = new int[MAX_N];
    private static long[]           width = new long[MAX_N + 1];
    private static long[]           area = new long[MAX_N + 1];
    private static int[]            l = new int[MAX_N], r = new int[MAX_N];
    private static int[]            stack = new int[MAX_N + 1];
    private static int[]            min = new int[MAX_N], max = new int[MAX_N];
    private static long[]           base = new long[MAX_N];
    private static boolean[]        used = new boolean[MAX_N];
    private static long[]           result = new long[MAX_N];
    private static int              N, pos, root;

    public static void main(String[] argv) throws Exception {
        readIn();
        solve();
    }

    private static void readIn() throws Exception {
        int top = 0, minH = Integer.MAX_VALUE;
        int i, x;
        N = nextInt();
        width[0] = area[0] = 0;
        for (i = 0; i < N; i++) {
            x = nextInt();
            height[i] = nextInt();
            width[i + 1] = width[i] + x;
            area[i + 1] = area[i] + (long) x * height[i];
            if (height[i] < minH) {
                minH = height[i];
                pos = i;
            }
            for (stack[top] = -1; top > 0 && height[stack[top - 1]] < height[i]; top--);
            if (top > 0) {
                r[stack[top - 1]] = i;
            }
            l[i] = stack[top] != -1 ? stack[top] : -1;
            r[i] = -1;
            stack[top++] = i;
        }
        root = stack[0];
    }

    private static void solve() {
        int top = 0;
        int i, x, y;
        stack[top++] = root;
        min[root] = 0; max[root] = N;
        base[root] = 0;
        while (top > 0) {
            x = stack[top - 1];
            if (!used[x]) {
                result[x] = base[x] + (width[max[x]] - width[min[x]]) * (height[x] + 1) - 
                       area[max[x]] + area[min[x]];
                used[stack[top - 1]] = true;
            }
            if ((y = getChild(x)) == 0) {
                top--;
            } else if (y < 0) {
                stack[top++] = l[x];
                min[l[x]] = min[x]; max[l[x]] = x;
                base[l[x]] = base[x] + (pos > x ? (width[max[x]] - width[x + 1]) * height[x] -
                        area[max[x]] + area[x + 1] : 0);
            } else {
                stack[top++] = r[x];
                min[r[x]] = x + 1; max[r[x]] = max[x];
                base[r[x]] = base[x] + (pos < x ? (width[x] - width[min[x]]) * height[x] -
                        area[x] + area[min[x]] : 0);
            }
        }
        for (i = 0; i < N; i++) {
            System.out.println(result[i]);
        }
    }

    private static int getChild(int x) {
        if (l[x] != -1 && !used[l[x]]) {
            return -1;
        } else if (r[x] != -1 && !used[r[x]]) {
            return 1;
        }
        return 0;
    }

    private static int nextInt() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return Integer.parseInt(st.nextToken());
    }

}

  1. if(j){
    int ans=a ;
    for(int x=j-1;x>=0;x–){
    if(!a ) break;
    ans=min(ans,a );
    sum+=ans;
    }
    }
    求解释,,dp的思路是什么呢?