---
tags: DP
title: 8/17 晚上解題1st, LIS
---

# Green Judge題目:
為了促進各位green judge解題速度，我會優先解答green judge的問題:grin:
<font color="#f00"></font>

| Green Judge Problem ID |
|------------------------------|
|<font color="#0f0">b026</font>|
|<font color="#0f0">b027</font>|
|<font color="#0f0">b032</font>|

# Solutions:
:::success

## b026
### 題目：[Green Judge b026](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b026)
### 方法一：
- 窮舉所有序列，（一共n(n+1)/2個序列）並將每個序列的元素(n)一一加總
- Time Complexity: $O(n^3)$

### 方法二：
- 預處理 $sum_i=\Sigma_{j=1}^{i}a_j$
- 利用前綴合優化元素和的部份，要求第 $i$ 到 $j$ 項的和只要用 $sum_j-sum_{i-1}$ 就好了
- Time Complexity: $O(n^2)$

### 方法三（最佳解）：
- 令 $dp_i$ 是以第i個元素為最右一個元素時的最大和
- 如果 $dp_{i-1} > 0$ ， $dp_i = dp_{i-1} + a_i$
- 如果 $dp_{i-1} <= 0$ ， $dp_i = a_i$
- 記得答案是 $max(dp_1, dp_2, ..., dp_n)$
- Time Complexity: $O(n)$
:::

:::success
## b027
### 題目：[Green Judge b027](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b027)
### 方法一：
- 窮舉邊長，從1到 $min(H, W)$ ，設邊長$k$
- 一共$(H-k+1)(W-k+1)$個邊長為k的正方形，
- 檢查每個正方形：$O(k^2)$
- Time Complexity: $O(HW * min(H, W)^3)$

### 方法二：
- 矩陣前綴和：
- 令$sum_{i,j} = \sum_{p=1}^{i}\sum_{q=1}^{j}a_{pq}$
- 求特定矩形和：
- $\sum_{p=a}^{b}\sum_{q=c}^{d}a_{pq}$
$= sum_{b,d} - sum_{a-1,d} - sum_{b,c-1} + sum_{a-1,c-1}$
- （媽呀就是排容原理）
- Time Complexity: $O(HW * min(H, W))$

### 方法三：
- 又來 DP 了～
- 令 $dp_{ij}$ 是以第 i, j 格為右下角的正方形最大邊長（這招常用喔～）
- 然後寫出遞迴式：
- 如果 $a_{ij} = 1$ （樹），$dp_{ij} = 0$
- 如果 $a_{ij} = 0$，$dp_{ij} = min(dp_{i-1,j}, dp_{i-1,j-1}, dp_{i-1,j-1})$
- Time Complexity: $O(HW)$
:::
:::success

## LIS (Longest Incresing Subsequence)

### 題目：[Green Judge b032](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b032)

### 方法一：
- 令 $dp_i$ 是以第 $i$ 項為結尾的 lis
- 對於所有 $j$ 滿足 $a_i > a_j$
- $dp_i = max\{dp_j\} + 1$
- Time Complexity: $O(n^2)$

### 方法二：
*適用條件：當lis長度一樣時，最後一個元素越小越好。*
*[必須用方法一 的 UVa 103](http://domen111.github.io/UVa-Easy-Viewer/?103)*
- 假設 $dp2_i$ 為lis的長度為 $i$ 時最後一個元素的最小值
- 可以發現 $dp2$ 為一個遞增序列！！
- 因為遞增，所以可以從左道右對於第 $i$ 個數字，在dp2這個序列裡二分搜第 $i$ 項的位置，便能找到以第 $i$ 項為結尾的 lis 長度
- 記得用第 $i$ 項更新 $dp2$ 喔～
- Time Complexity: $O(nlogn)$

### 求LIS的方法很多，講不完～

- 練習題：
給一些座標點，請找出最長序列S滿足（對於每個i）
s[i].x < s[i+1].x && s[i].y < s[i+1].y
:::
:::info
## 作業：
*題目不難，至少選兩題寫喔～*
[PA UVa 437](http://domen111.github.io/UVa-Easy-Viewer/?437)
[PB UVa 481](http://domen111.github.io/UVa-Easy-Viewer/?481)
[PC UVa 10534](http://domen111.github.io/UVa-Easy-Viewer/?10534)
[PD TIOJ 1907](https://tioj.ck.tp.edu.tw/problems/1907)
[PE UVa 103](http://domen111.github.io/UVa-Easy-Viewer/?103)
:::