[Java] UVa 1062 Containers

題目連結

題意:
只知道跟船阿貨運有關係XD
題目給定一個 A ~ Z 組成的序列
(由小到大)
輸出該序列的最長遞增子序列 (LIS) 的長度

舉例:
ABAADEF
LIS 為 ABDEF，輸出 5

LIS 不一定要是連續的
而且為嚴格遞增
也就是任意前必小於後
(不能有重複)

像題目的 CBACBACBACBACBA
LIS 為 ABC，輸出 3
不能為 AABC 或 ABBC 之類的

解法:
用一個陣列 LIS[ ]
紀錄以某元素為結尾的 LIS 長度
由前而後 Greedy 掃一遍即可

舉例:
ABADEF，預設都是 1

以 B 為準，往前掃到 A
可以接在 A後面
B 的 LIS 就可以是 A 的 +1
不過若 B 本來就比較大，就不更動

程式(Java):

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int C = 1;
	while (sc.hasNext()) {
	String s = sc.nextLine();
	if (s.equals("end"))
	break;
	int LIS[] = new int[s.length()];
	Arrays.fill(LIS, 1);
	int max = 0;
	for (int i = 0; i < s.length(); i++) {
	for (int j = i - 1; j >= 0; j--)
	if (s.charAt(j) < s.charAt(i))
	LIS[i] = (LIS[i] > LIS[j]+1) ? (LIS[i]) : (LIS[j]+1);
	if (LIS[i] > max)
	max = LIS[i];
	}
	System.out.println("Case " + (C++) + ": " + max);
	}
	}
	}

view raw UVa1062.java hosted with ❤ by GitHub