# 演算法課程題解 - 動態規劃\: 最長遞增子序列 LIS

# UVa 497
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?497

敵國發射了洲際飛彈過來，然而我們的反飛彈系統有嚴重的缺陷，發射角只能生不能降
也就是說每次你只能摧毀比上一枚摧毀的飛彈還高的飛彈
現在告訴你飛彈的高度依序是多少，請問你最多能擋下多少飛彈?
請依序輸出攔截的飛彈高度

## 想法 By Koios
每次都只能選擇比上次更高的高度，所以如果把全部的飛彈高度當作是一個序列來看，題目等同於要求最長的遞增子序列長度
對於每個序列的元素，都可以選擇要成為新遞增子序列的開頭或是舊遞增子序列的一部分
如果要成為舊遞增子序列的一部分，那麼首先我們的值要比序列尾端的值還要大
當我們找出所有可以跟我們接在一起的舊遞增子序列，那麼我就知道我最長可以是多少

根據上面的討論可以得出簡單的 dp 式
定義 $dp[i]$ 表示以第 $i$ 項作結尾的 LIS 最長長度
則有轉移式
$$
dp[i] = max(dp[j]) + 1 \quad \texttt{(arr[i] > arr[j]) && j < i}
$$
並且所有 $dp$ 值最少都有 $1$ ，也就是自己本身

至於回朔攔截的飛彈高度，在 DP 的過程當中我們就可以知道 $i$ 是從哪個 $j$ 轉移過來的，最後就可以簡單遞迴輸出

:::warning
如果你跟我一樣採用 getline 的方式讀取每個數字輸入，請記得要轉換回數字的樣子
:::

### 程式碼

//By Koios1143
#include<iostream>
using namespace std;
int T, dp[10005], from[1005], arr[10005], last, ans;
string tmp;

void print_ans(int p){
	if(from[p] != -1){
		print_ans(from[p]);
	}
	cout<<arr[p]<<"\n";
}

int to_int(string s){
	int res=0;
	for(int i=0 ; i<s.size() ; i++){
		res *= 10;
		res += s[i]-'0';
	}
	return res;
}

int main(){
	while(cin>>T){
		cin.ignore();
		cin.ignore();
		for(int Case=0 ; Case<T ; Case++){
			int N=0;
			while(getline(cin, tmp) && tmp != ""){
				arr[N++] = to_int(tmp);
			}
			ans = 0;
			last = 0;
			for(int i=0 ; i<N ; i++){
				// dp 最少也會是 1
				dp[i] = 1;
				from[i] = -1;
				for(int j=i-1 ; j>=0 ; j--){
					// 不直接以 DP 式的 max 表示，而是找到最大，方便記錄回朔
					if(arr[i] > arr[j] && dp[j]+1 > dp[i]){
						dp[i] = dp[j] + 1;
						from[i] = j;
					}
				}
				if(dp[i] > ans){
					last = i;
					ans = dp[i];
				}
			}
			if(Case) cout<<"\n";
			cout<<"Max hits: "<<ans<<"\n";
			print_ans(last);
		}
	}
	
	return 0;
}

### 時間複雜度分析
DP 每個狀態轉移時間複雜度可估計為 $N$，雖然實際上會比較小
總共有 $N$ 個狀態，DP 總時間複雜度為 $O(N^2)$

###### tags: `SCIST 演算法 題解`