想吃冰卻又敏感保護不足?來自星星的你也會打廣告?法人:14檔今年本業虧定了24天後重啟院會 兩岸...
2013-12-11 07:57:03 人氣(44) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][dp] 11499 - Longest Increasing Sequence

0
收藏
0
推薦


 Longest Increasing Sub-sequence 

The Problem

The problem of determining the longest increasing sub-sequence in a list of numbers is already a classic in programming competitions. Despite this fact, that is the problem you must solve here. But, in order to avoid having you yawning while solving the problem, we introduced a small change: the list of numbers will be given as a bidimensional matrix, and the increasing sequence must be "embedded" in a submatrix of the original matrix.

Let's define the problem more precisely. The linearization of a bidimensional matrix is the concatenation of its lines, from the first to the last. A submatrix is a rectangular region of a bidimensional matrix (with sides paralel to the sides of the matrix). The size of a submatrix is its number of elements. You must write a program that, given a matrix of integers, determines the largest submatrix such that, when linearized, results in an increasing sequence. The figure below shows some examples of submatrices of largest size which contain increasing sequences. Notice that more than one such a submatrix may exist in a given matrix.

The Input

The input contains several test cases. The first line of a test case contains two integers N and M indicating the matrix dimensions (1 ≤ N,M ≤ 600). Each of the next N lines contains M integers, separated by a space, describing the elements of the matrix. Element Xi,j of the matrix is the j-th integer of the i-th line in the input (-106 ≤ Xi,j ≤ 106).

The end of input is indicated by a line containing only two zeros, separated by a space.

The Output

For each test case in the input your program must print one single line, containing the size of the largest sub-matrix that, when linearized, results in an increasing sequence.

Sample Input

3 3
1 2 5
4 6 7
10 8 3
3 4
1 2 1 2
9 6 7 3
8 7 2 8
4 2
-23 -12
0 2
16 15
57 33
4 4
2 2 2 2
2 2 2 2
2 2 2 2
2 2 2 2
0 0

Sample Output

4
3
4
1

題目描述:

找一個嚴格遞增的子矩陣,嚴格遞增的方式依序讀每一行,所造成得的遞增。

而不是矩陣內每個元素嚴格大於左方和上方。

題目解法:

一開始誤會題目了,總之以下做法在 O(n^3) 完成。
任舉兩列,然後用 greedy 的方式由上方掃描到下方,
中間使用 DP 的方式去計算這兩列之間的元素是否遞增。

如果能加入跳躍表應該能更加地快速。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int n, m, g[605][605];
int main() {
    int i, j, k;
    while(scanf("%d %d", &n, &m) == 2) {
        if(n+m == 0)
            break;
        for(i = 0; i < n; i++)
            for(j = 0; j < m; j++)
                scanf("%d", &g[i][j]);
        int ret = 0;
        for(i = 0; i < m; i++) {
            int sum[605] = {};
            for(j = i; j < m; j++) {
                int height = j - i + 1;
                int l = 0, r = 0;
                for(k = 0; k < n; k++) {
                    if(height == 1)
                        sum[k] = 1;
                    else {
                        if(g[k][j] > g[k][j-1])
                            sum[k]++;
                    }
                    r = k;
                    if(r-1 >= l && g[r-1][j] >= g[r][i])
                        l = max(l, k);
                    if(sum[k] != height) l = max(l, k+1);
                    ret = max(ret, (r-l+1)*height);
                }
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}

11499Longest Increasing Sequencedp
台長:Morris
人氣(44) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA][線段交] 393 - The Doors
此分類上一篇:[UVA] 10441 - Catenyms

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文