Poj 1631 Bridging signals(二分+DP 解 LIS)

题意：题目很难懂，题意很简单，求最长递增子序列LIS。

分析：本题的最大数据40000，多个case。用基础的O(N^2)动态规划求解是超时，采用O(n*log2n)的二分查找加速的改进型DP后AC了。

在基础的动态规划解法中，由于动态规划的无后效性（对于每个阶段来说，它以前的各阶段状态无法直接影响它未来的决策，只能间接地通过当前状态来影响），当我们考察第i+1个元素的时候，我们是不考虑前面i个元素的分布情况的。当我们考虑前面的情况时会发现，对于前面i个元素的任意一个递增子序列，如果这个子序列的最大元素比Array[i+1]小，那么就可以将Array[i+1]加在这个子序列后面，构成一个新的递增子序列。因此我们希望找到前i个元素的一个递增子序列。使得这个递增子序列的最大元素尽可能地小，且长度尽可能地长。这个确定的过程就可以用二分查找加速。

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

public class Main {

	static int BinSearch(int a[], int length, int s) {

		int left = 0, right = length - 1, mid = 0;

		while (left <= right) {

			mid = (left + right) / 2;

			if (a[mid] <= s) {

				left = mid + 1;

			} else {

				right = mid - 1;

			}

		}

		return left;

	}

	static int[] MaxV = new int[40001];

	static int getLIS(int[] arr, int size) {

		MaxV[0] = arr[0];

		int len = 1;

		for (int i = 1; i < size; ++i) {

			if (arr[i] > MaxV[len - 1]) {

				MaxV[len++] = arr[i];

			} else {

				int pos = BinSearch(MaxV, len, arr[i]);

				MaxV[pos] = arr[i];

			}

		}

		return len;

	}

	public static void main(String[] args) throws NumberFormatException,

			IOException {

		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int cases = Integer.parseInt(br.readLine());

		int n;

		int a[] = new int[40001];

		while (cases-- != 0) {

			n = Integer.parseInt(br.readLine());

			for (int i = 0; i < n; i++) {

				a[i] = Integer.parseInt(br.readLine());

			}

			System.out.println(getLIS(a, n));

		}

	}

}

巴特西

Poj 1631 Bridging signals(二分+DP 解 LIS)

最新文章

热门文章