(1) 最长上升子序列问题

问题描述

一个序列有$n$个元素$x_1, x_2, x_i, \dots,x_n$，请求出它的最长上升子序列.

状态(问题定义)

$f[i]$，以第$i$个元素结尾的最长上升子序列的长度

初始化

$f[1]$~$f[n]$ 为1

状态转移方程

$$f[i] = \max(f[i], f[j] + 1) \quad \text{for } j < i \text{ and } x_i > x_j$$

$i:1~n$ $j:1~i-1$

答案

从$f[1]$~$f[n]$取出最大值

(2) 最大连续子序列和

问题描述

一个序列有$n$个元素$x_1, x_2, x_i, \dots,x_n$，求出连续子序列和最大

状态(问题定义)

$f[i]$，以第$i$个元素结尾连续子序列和最大

初始化

$f[1]$~$f[n] = x_i$

状态转移方程

$$f[i] = \max(f[i-1] + x_i, x_i)$$

$i:1~n$ $j:1~i-1$

答案

从$f[1]$~$f[n]$取出最大值

(2) 选取元素问题

问题描述

一个序列有$n$个元素$a_1, a_2, a_i, \dots,a_n$，可以从这个序列中选取若干的元素使他们的和最大，但是不能选取连续的三个元素.

状态(问题定义)

$f[i][0]$，前$i$个元素，第$i$个元素不选能获得最大值 $f[i][1]$，前$i$个元素，第$i$个元素选取能获得最大值

初始化

$f[0][0] = 0$，其他元素都是$-10^9$

状态转移方程

$$f[i][0] = \max(f[i-1][0], f[i][0]) \quad \text{(第i个元素不选, 第i-1个元素不选)}$$$$f[i][0] = \max(f[i-2][0] + a[i-1], f[i][0]) \quad \text{(i-2>=0) (第i个元素不选, 第i-1个元素选, 第i-2 元素不选)}$$$$f[i][0] = \max(f[i-3][0] + a[i-1] + a[i-1], f[i][0]) \quad \text{(i-3>=0) (第i个元素不选, 第i-1个元素选, 第i-2 元素选, i-3 元素不选)}$$$$f[i][1] = \max(f[i-1][0] + a[i], f[i][1]) \quad \text{(第i-1个元素不选)}$$$$f[i][1] = \max(f[i-2][0] + a[i] + a[i-1], f[i][1]) \quad \text{(i-2>=0) (第i-1个元素选, 第i-2元素不选)}$$

$i:1 \sim n$

答案

$\max(f[n][0], f[n][1])$

(3) 元素分组问题

问题描述

一个序列有$n$个元素$a_1, a_2, a_i, \dots,a_n$，把这些元素分成若干组，每一组都是有连续的元素组成，让每组元素之和大于等于0，分成尽可能多的组.

状态(问题定义)

$f[i]$ 前$i$个元素最多能分成多少组 $sum[i]$ 前$i$个元素的和

初始化

$f[0]=0$，$f[1]$~$f[n]$ 为$-10^9$

状态转移方程

$$f[i] = \max(f[j] + 1, f[i]) \quad \text{for } j < i \text{ and } sum[i] - sum[j] \geq 0$$

$i:1 \sim n$ $j:0\sim i-1$

答案

$f[n] < 0$ 无答案，$f[n] \geq 0$ 答案为$f[n]$