零动态规划的定义

斐波那契数列： $f_i= f_{i-1} + f_{i-2}$

1 1 2 3 5 8 13 21 34 55 ….

项： $f_i$

递推式： $f_i = f_{i-1} + f_{i-2}$

起始项： $f_1 = 1$ $f_2 = 1$

目标： $f_n$

动态规划：更加复杂的递推式

状态：递推项

状态转移方程：递推式

边界：起始项

目标：目标

一线性DP

1 背包问题

I.01背包

$n$ :件数 $v$ :背包容量 $c_i$ :第i件物品体积 $wi$ :第i件物品价值

状态: $f_{i,j}$ :将前 $i$ 件物品放入一个容量为 $j$ 的背包能获得的最大价值

状态转移方程：

$f_{i,j}=\begin{cases}f_{i-1,j}&j<c_i\\\max(f_{i-1,j},f_{i-1,j-c_i}+w_i)&j>=c_i\end{cases}$

边界： $f_{0,j} = 0$ $(0<=j<=v)$

目标： $f_{n,v}$

$Code$

#include <iostream>
using namespace std;

int n, v, c[110], w[110], f[110][1010]; 

int main() {
    cin >> v >> n;
    for (int i=1; i<=n; i++)
        cin >> c[i] >> w[i];
    for (int i=1; i<=n; i++)
        for (int j=0; j<=v; j++)
            if (c[i] <= j)
                f[i][j] = max(f[i-1][j], f[i-1][j-c[i]]+w[i]);
            else
                f[i][j] = f[i-1][j];
    cout << f[n][v] << endl;
    return 0;
}

01背包的降维

状态： $f_j$ :一个容量为j的背包能装得的最大价值

状态转移方程：

$f_j = \max(f_j, f_{j-c_i}+w_i)$ $(j >= c_i)$

边界： $f_i = 0$ $(0 <= i <= v)$

目标： $f_v$

$Code$

#include <iostream>
using namespace std;

int n, v, c[110], w[110], f[1010]; 

int main() {
    cin >> v >> n;
    for (int i=1; i<=n; i++)
        cin >> c[i] >> w[i];
    for (int i=1; i<=n; i++)
        for (int j=v; j>=c[i]; j--)
            f[j] = max(f[j], f[j-c[i]]+w[i]);
    cout << f[v] << endl;
    return 0;
}

例题

题目描述 Description
妈妈买了N个糖果，想要分给她的双胞胎的孩子（糖果要分成两份）。每个糖果有一个受欢迎程度，用一个整数表示。为了避免不必要的争吵，弟弟和哥哥分得的糖果的受欢迎程度之差必须是一个最小值，且糖果必须全部分完。你能帮帮这位妈妈吗？

输入描述 Input Description
第一行一个整数n，表示糖果数据。
第二行n个数Wi，表示糖果的受欢迎程度，用空格隔开。

输出描述 Output Description
输出分成两堆糖果后的受欢迎程度差的绝对值。

样例输入 Sample Input
5
5 8 13 27 14

样例输出 Sample Output
3

数据范围及提示 Data Size & Hint
N (1 ≤ N ≤ 2000)
Wi (1 ≤ Wi ≤ 100)

$Solution$

将总重量的一半看为背包容量，往里面放东西，其中能放到最多的容量是为其中某一个人的糖果受欢迎程度，再拿另一个减掉即可。

$Code$

#include <iostream>
using namespace std;

int n, v, f[100010], w[10010];

int main() {
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> w[i];
        v += w[i];
    }
    for (int i=1; i<=n; i++)
        for (int j=v/2; j>=w[i]; j--)
            f[j] = max(f[j], f[j-w[i]]+w[i]);
    cout << v-2*f[v/2] << endl;
    return 0;
}

2 最长不下降子序列（ $LIS$ ）

状态： $f_i$ ：以 $a_i$ 结尾的最长不下降子序列的长度

或:前 $i$ 个数，必取 $a_i$ ,能得到的最长不下降子序列的长度

状态转移方程：

$f_i = \max\{f_j+1\}$ $(1 <= j < i, a_j <= a_i)$

边界： $f_i = 1$

目标： $\max\{f_i\}$

$Code$

#include <iostream>
using namespace std;

int n, a[10010], f[10010], ans;

int main() {
    for (int i=1; i<=n; i++)
        cin >> a[i];
    for (int i=1; i<=n; i++) {
        f[i] = 1;
        for (int j=1; j<i; j++)
            if (a[i] > a[j] && f[j]+1 > f[i])
                f[i] = f[j]+1;
        ans = max(ans, f[i]);
    }
    cout << ans << endl;
    return 0;
}

求出最长不下降子序列

其实思想并不难，用 $b_i$ 来表示最长不下降子序列的前驱，递归输出即可。

$Code$

#include <iostream>
using namespace std;

int n, a[10010], f[10010], b[10010], start, ans;

//打印以x下标结尾的最长不下降子序列

//第一种
void print_1(int x) {
    if (x == 0)        return ;
    print_1(b[x]);
    cout << a[x] << " ";
}

//第二种
void print_2(int x) {
    if (b[x] == 0) {
        cout << a[x] << " ";
        return ;
    }
    print_2(b[x]);
    cout << a[x] << " ";
}

int main() {
    cin >> n;
    for (int i=1; i<=n; i++)
        cin >> a[i];
    for (int i=1; i<=n; i++) {
        f[i] = 1;
        for (int j=1; j<i; j++)
            if (a[i] >= a[j] && f[j]+1 > f[i]) {
                f[i] = f[j]+1;
                b[i] = j;
            }
        if (f[i] > ans) {
            ans = f[i];
            start = i;
        }
    }
    print_1(start);
    cout << endl;
    print_2(start);
    cout << endl;
    return 0;
}

求出降序序列的种类数

思路有些复杂：逆序求解， $b_i$ 表示以 $a_i$ 结尾的最长下降序列的种类数，其中有可能会出现重复情况，所以用 $last$ 记录上一次更新的下标，如果重复则不更新。

$Code$

#include <iostream>
using namespace std;

int n, a[5005], f[5005], b[5005], last, ans, ans2;

int main() {
    cin >> n;
    for (int i=1; i<=n; i++)
        cin >> a[i];
    for (int i=n; i>=1; i--) {
        last = 0;
        f[i] = 1;
        b[i] = 1;
        for (int j=i+1; j<=n; j++) {
            if (a[i] > a[j]) {
                if (f[j]+1 > f[i]) {
                    f[i] = f[j]+1;
                    b[i] = b[j];
                    last = j;
                }
                else if (f[j]+1 == f[i] && a[j] != a[last]) {
                    b[i] += b[j];
                    last = j;
                }
            }
        }
        if (f[i] > ans) ans = f[i];
    }
    last = 0;
    for (int i=1; i<=n; i++) {
        if (f[i] == ans && a[i] != a[last]) {
            ans2 += b[i];
            last = i;
        }
    }
    cout << ans << " " << ans2 << endl;
    return 0;
}

例题

例题一

题目描述 Description
Smart很喜欢读书，为了安排自己的读书计划，他会预先把要读的内容做好标记， A B表示一个页段，即第A到B面，当然A<B，若有两个页段A-B，B-C，则可以直接记为A-C，这样，他就可以一次看完，现在告诉你n个页段，请你帮他求出最长的一条页段，并输出这条页段的长度和组成它的页段个数。举个例子：

有 6 个页段：

2-7 1-3 3-12 12-20 7-10 4-50

那么连续的页段就有：

1-3，3-12，12-20长度为20-1+1=20由3个页段组成；

2-7，7-10长度为10-2+1=9由2个页段组成；

4-50长度为50-4+1=47由1个页段组成；

那么最长的一条就是第三个，所以结果为47 1。

需要注意的是:如果有两条不一样的连续的页段长度同时为最大，那么取组成页段数多的一条。

例子: 1-5，5-10，1-10

输出: 10 2

输入描述 Input Description
第一行为一个整数n；
第2行到第n+1行，每行两个整数A B，记录一个页段的信息。

输出描述 Output Description
输出一个整数，即最长的页段的长度和组成它的页段数。

样例输入 Sample Input
7
1 5
10 12
3 10
2 7
2 10
12 16
7 9

样例输出 Sample Output
15 3

数据范围及提示 Data Size & Hint
30%的数据：n<20，0≤A<B≤500；
100%的数据：n≤500，0≤A<B≤500。

$Solution$

首先为了保持有序，建立结构体：

struct book {
    int st, ed, len;
};

其中 $st$ 表示页段起点， $ed$ 表示页段终点， $len$ 表示页段长度。

按起点大小先排序，之后再仿照 $LIS$ 问题，列方程：

令 $f_i$ 为以第 $i$ 个页段为结尾能阅读的最长页码，得：

$f_i = \max(f_i,f_j+a_i.len)$ ( $1<=j<i,a_i.st=a_j.ed$ )

又因为题目要求我们输出页段个数，所以再建一个 $b_i$ ，表示以第 $i$ 个页段为结尾能阅读的最长页码所需的页段个数，则有：

$b_i =\begin{cases}b_j+1&f_j>f_i\\\max(b_i,b_j+1)&f_j=f_i\end{cases}$

于是就解决了。

$Code$

#include <iostream>
#include <algorithm>
using namespace std;

struct book {
    int st, ed, len;
};
book a[10010];
bool cmp(book x, book y) {
    return x.st < y.st;
}

int f[10010], b[10010], n, ans, res;

int main() {
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> a[i].st >> a[i].ed;
        a[i].len = a[i].ed - a[i].st;
    }
    sort(a+1, a+1+n, cmp);
    for (int i=1; i<=n; i++) {
        f[i] = a[i].len;
        b[i] = 1;
        for (int j=1; j<i; j++) {
            if (a[i].st == a[j].ed && f[j]+a[i].len > f[i]) {
                f[i] = f[j]+a[i].len;
                b[i] = b[j]+1;
            }
            else if (a[i].st == a[j].ed && f[j]+a[i].len == f[i])
                b[i] = max(b[i], b[j]+1);
        }
        ans = max(ans, f[i]);
    }
    for (int i=1; i<=n; i++)
        if (f[i] == ans)
            res = max(res, b[i]);
    cout << ans+1 << " " << res << endl;
    return 0;
}

例题二

传送门

$Solution$

没什么难点，跟上一题差不多，反而简单一点，唯一不同的就是 $a_i.st==a_j.ed$ 改为： $ai.st>=aj.ed$ 即可

$Code$

#include <iostream>
#include <algorithm>
using namespace std;

struct speak{
    int st, ed, len;
};//结构体更方便推算和排序
speak a[10010];
bool cmp(speak x, speak y) {
    return x.st < y.st;
}//自定义cmp函数，用来排序。如果想要更快可重载运算符

int n, f[10010], ans;

int main() {
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> a[i].st >> a[i].ed;
        a[i].len = a[i].ed-a[i].st;//时间计算式
    }
    sort(a+1, a+1+n, cmp);
    for (int i=1; i<=n; i++) {
        f[i] = a[i].len;//初始化：假设在它前面没有演讲，最短时间也是这个演讲的时间
        for (int j=1; j<i; j++) {
            if (a[j].ed <= a[i].st && f[i] < f[j]+a[i].len)
                f[i] = f[j]+a[i].len;
        }
        ans = max(ans, f[i]);//更新答案
    }
    cout << ans << endl;
    return 0;
}

例题三

n个矩阵排一行。当矩阵a长宽或者宽长小于矩阵b的长宽或者宽长时我们称作矩阵a可以嵌套在矩阵b中。例如（1,2）可以嵌套在（2,3）内，但不能嵌套在（3,1）中。选出一行矩阵，使得每一个矩形都可以嵌套在下一个矩形内（最后一个除外）。
输出一个数，表示最多符合条件的矩形数目

$Solution$

将 $LIS$ 变成了二维。

其实只要按照长、宽两个关键字来作为“不下降”的指标即可。

但是要注意，有可能矩阵可以翻转，也就是长和宽可以互换。

令 $f_i$ 为前 $i$ 个矩阵，以第 $i$ 个矩阵作为最外面的一个矩阵，最多能嵌套的矩阵数量。

$f_i = \max(f_i,f_j+1)$ $(1<=j<i)$ $a_i.x>a_j.x$ 并且 $a_i.y>a_j.y$ 或 $a_i.x>a_j.y$ 并且 $a_i.y>a_j.x$

当然，还要排序。因为长和宽可以互换，所以没有唯一的关键字，就应该按面积排序。

$Code$

#include <iostream>
#include <algorithm>
using namespace std;

struct juxing {
    int x, y;
};
juxing a[10010];
bool cmp(juxing m, juxing n) {
    return m.x*m.y < n.x*n.y;
}

int n, f[10010], ans;

int main() {
    cin >> n;
    for (int i=1; i<=n; i++)
        cin >> a[i].x >> a[i].y;
    sort(a+1, a+1+n, cmp);
    for (int i=1; i<=n; i++) {
        f[i] = 1;
        for (int j=1; j<i; j++) {
            if ( ((a[i].x>a[j].x&&a[i].y>a[j].y) || (a[i].x>a[j].y&&a[i].y>a[j].x)) && f[j]+1>f[i]) {
                f[i] = f[j]+1;
            }
        }
        ans = max(ans, f[i]);
    }
    cout << ans << endl;
    return 0;
}

例题四

题目描述 Description
现在给出n个各不相同的正整数，现在要求从这n个正整数抽出若干个正整数出来，将它们排成从小到大的序列。使得这个序列中任意两个相邻的数之和都是素数。请问这个序列最多能有多少个数字？
输入描述 Input Description
第一行，一个正整数，n
第二行，n个各不相同的正整数，a1 a2 ... an

输出描述 Output Description
第一行，满足条件的序列中数字最多的个数

样例输入 Sample Input
10
9 17 8 5 14 12 13 25 27 30

样例输出 Sample Output
6

数据范围及提示 Data Size & Hint
n<=1000，每个整数ai<=1000
题目保证最长序列中不止有一个数字

$Solution$

考虑运用 $LIS$ 的思想。

因为要从小到大，所以先将原数组排序，再定义 $f_i$ 表示前 $i$ 个数，必取 $a_i$ ，相邻的数字和为素数的子序列最长长度。

状态转移方程：

$f_i=\max\{f_j+1\}(a_i+a_j$ $is$ $prime,1<=j<i)$

边界： $f_i=1$

目标： $\max\{f_i\}$

$Code$

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int n, a[10010], f[10010], ans;

bool is_prime(int x) {
    if (x == 0 || x == 1)
        return false;
    for (int i=2; i<=sqrt(x); i++)
        if (x % i == 0)
            return false;
    return true;
}

int main() {
    cin >> n;
    for (int i=1; i<=n; i++)
        cin >> a[i];
    sort(a+1, a+1+n);
    for (int i=1; i<=n; i++) {
        f[i] = 1;
        for (int j=1; j<i; j++) {
            if (is_prime(a[i]+a[j])) f[i] = max(f[i], f[j]+1);
        }
        ans = max(ans, f[i]);
    }
    cout << ans << endl;
    return 0;
}

3 最长公共子序列( $LCS$ )

$f_{i,j}$ : $A$ 序列的前 $i$ 个元素和 $B$ 序列的前 $j$ 个元素能得到的 $LCS$ 长度

状态转移方程：

$f_{i,j}=\begin{cases}f_{i-1,j-1}+1&A_i=B_j\\\max(f_{i-1,j},f_{i,j-1})&A_i≠B_j\end{cases}$

边界： $f_{i,0}=f_{0,j}=0$

目标： $f_{m,n}$

$Code$

#include <iostream>
#include <string>
using namespace std;

string A, B;
int m, n, f[110][110];

int main() {
    cin >> A >> B;
    m = A.size(), n = B.size();
    A = ' '+A, B = ' '+B;
    for (int i=1; i<=m; i++)
        for (int j=1; j<=n; j++)
            if (A[i] == B[j])
                f[i][j] = f[i-1][j-1]+1;
            else
                f[i][j] = max(f[i-1][j], f[i][j-1]);
    cout << f[m][n] << endl;
    return 0;
}

4 最长公共子上升子序列( $LCIS$ )

$f_{i,j}$ ：序列 $a$ 的前 $i$ 个元素和序列 $b$ 的前 $j$ 个元素必取 $b_j$ 的 $LCIS$ 的长度

状态转移方程：

$f_{i,j}=\begin{cases}\max\{f_{i-1,k}\}+1&&a_i=b_j,1<=k<j,b_k<b_j\\ f_{i-1,j}&&a_i≠b_j\end{cases}$

边界： $f_{i,0}=f_{0,j}=0$

目标： $\max\{f_{m,j}\}$ $(1<=j<n)$

时间复杂度： $O(n^2m)$

$Code$

#include <iostream>
using namespace std;

int a[3010], b[3010], n, m, f[3010][3010], ans;

int main() {
    cin >> n;
    for (int i=1; i<=m; i++)
        cin >> a[i];
    for (int j=1; j<=n; j++)
        cin >> b[j];
    for (int i=1; i<=m; i++) {
        for (int j=1; j<=n; j++) {
            if (a[i] == b[j]) {
                int res = 0;
                for (int k=1; k<j; k++) 
                    if (b[k] < b[j]) res = max(res, f[i-1][k]);
                f[i][j] = res+1;
            }
            else f[i][j] = f[i-1][j];
        }
    }
    for (int j=1; j<=n; j++)
        ans = max(ans, f[m][j]);
    cout << ans << endl;
    return 0;
}

5 数塔问题

$f_{i,j}$ ：第 $i$ 行第 $j$ 列这个数到数塔顶端能得到的路径上数字之和的最大值

状态转移方程：

$f_{i,j}=\max(f_{i+1,j},f_{i+1,j+1})+a_{i,j}$

边界： $f_{n,j}=a_{n,j}$

目标： $f_{1,1}$

反着推也可以。

$Code$

//正着推
#include <iostream>
using namespace std;

int n, f[1010][1010], a[1010][1010]; 

int main() {
    cin >> n;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=i; j++)
            cin >> a[i][j];
    for (int j=1; j<=n; j++)
        f[n][j] = a[n][j];
    for (int i=n-1; i>=1; i--)
        for (int j=1; j<=i; j++)
            f[i][j] = max(f[i+1][j], f[i+1][j+1]) + a[i][j];
    cout << f[1][1] << endl;
    return 0;
}

//反着推
#include <iostream>
using namespace std;

int f[1010][1010], n, a[1010][1010], ans;

int main(){
    cin >> n;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=i; j++)
            cin >> a[i][j];
    f[1][1] = a[1][1];
    for(int i=2; i<=n; i++)
        for(int j=1; j<=i; j++)
            f[i][j] = max(f[i-1][j], f[i-1][j-1]) + a[i][j];
    for(int j=1; j<=n; j++)
        ans = max(f[n][j], ans);
    cout << ans << endl;
    return 0;
}

降维

也不难。

$f_j$ 表示第 $j$ 列能得到的路径数字最大和。

状态转移方程：

$f_j =\max(f_j,f_{j+1})+a_{i,j}$

边界： $f_j=a_{n,j}$

目标： $f_1$

$Code$

#include <iostream>
using namespace std;

int n, f[1010], a[1010][1010]; 

int main() {
    cin >> n;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=i; j++)
            cin >> a[i][j];
    for (int j=1; j<=n; j++)
        f[j] = a[n][j];
    for (int i=n-1; i>=1; i--)
        for (int j=1; j<=i; j++)
            f[j] = max(f[j], f[j+1]) + a[i][j];
    cout << f[1] << endl;
    return 0;
}

求出路径

令 $b_{i,j}$ 记录第 $i$ 行第 $j$ 列的路径前驱为第 $i+1$ 行的那一列，输出即可。

$Code$

#include <iostream>
using namespace std;

int n, b[1010][1010], f[1010][1010], a[1010][1010];

int main() {
    cin >> n;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=i; j++)
            cin >> a[i][j];
    for (int j=1; j<=n; j++)
        f[n][j] = a[n][j];
    for (int i=n-1; i>=1; i--)
        for (int j=1; j<=i; j++) {
            if (f[i+1][j] > f[i+1][j+1]) {
                f[i][j] = f[i+1][j]+a[i][j];
                b[i][j] = j;
            }
            else {
                f[i][j] = f[i+1][j+1]+a[i][j];
                b[i][j] = j+1;
            }
        }
    int k = 1;
    for (int i=1; i<=n; i++) {
        cout << a[i][k] << " ";
        k = b[i][k];
    }
    cout << endl;
    return 0;
}

6 最大连续子数组和

朴素方法：前缀和。

时间复杂度： $O(n^2)$

$Code$

#include<iostream>
using namespace std;

int n, a[10010], s[10010];

int main() {
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> a[i];
        s[i] = s[i-1]+a[i];
    }
    for (int i=2; i<=n; i++)
        for (int j=1; j<i; j++)
            ans = max(ans, s[i]-s[j]);
    cout << ans << endl;
    return 0;
}

优化

考虑 $DP$

$f_i$ 前 $i$ 个数字必取 $a_i$ 的情况下能得到的最大连续子数组的和。

$f_i=\max(f_{i-1}+a_i,a_i)$

边界： $f_0=0$

目标： $\max\{f_i\}$ $1<=i<=n$

时间复杂度： $O(n)$

$Code$

#include <iostream>
using namespace std;

int n, a[100010], f[100010], ans = -1e9;

int main() {
    cin >> n;
    for (int i=1; i<=n; i++)
        cin >> a[i];
    f[0] = 0;
    for (int i=1; i<=n; i++) {
        f[i] = max(f[i-1]+a[i], a[i]);
        ans = max(ans, f[i]);
    }
    cout << ans << endl;
    return 0;
}

求数字个数

令 $b_i$ 为以 $a_i$ 为结尾最大连续子数组和的数字个数，则有：

$b_i=\begin{cases}b_{i-1}+1&f_{i-1}+a_i>=a_i\\1&f_{i-1}+a_i<a_i\end{cases}$

$Code$

#include <iostream>
using namespace std;

int n, a[100010], f[100010], ans = -1e9, b[100010], len;

int main() {
    cin >> n;
    for (int i=1; i<=n; i++)
        cin >> a[i];
    f[0] = 0;
    for (int i=1; i<=n; i++) {
        if (f[i-1]+a[i] >= a[i]) {
            f[i] = f[i-1]+a[i];
            b[i] = b[i-1]+1;
        }
        else {
            f[i] = a[i];
            b[i] = 1;
        }
        if (ans < f[i]) {
            ans = f[i];
            len = b[i];
        }
    }
    cout << ans << " " << len << endl;
    return 0;
}

环形数组最大连续子数组和

朴素方法：还是前缀和 $QAQ$

时间复杂度：还是 $O(n^2)QAQ$

$Code$

#include <iostream>
using namespace std;

int n, s[10010], a[10010], ans = -1e9;

int main() {
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> a[i];
        a[i+n] = a[i];
    }
    for (int i=1; i<=2*n; i++)
        s[i] = s[i-1]+a[i];
    for (int i=0; i<=n-1; i++)
        for (int j=i+1; j<=i+n; j++)
            ans = max(ans, s[j]-s[i]);
    cout << ans << endl;
    return 0;
}

优化

仍是 $DP$

我们发现，环形数组子数组最大和有可能不在环上，也有可能在环上。

所以只要求环上最大和和非环上最大和的最大值即可。

非环上最大和很好求，而环上最大和只需要总和减掉最小连续子数组和即可。

而想求最小连续子数组和，只需要将数字取反，求过之后再取反，即可。

$Code$

#include <iostream>
using namespace std;

const int INF = 1e9;

int n, sum, a[10010], b[10010], f[10010], g[10010], ans1 = -INF, ans1 = -INF;

int main() {
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> a[i];
        b[i] = -a[i];
        sum += a[i];
    }
    for (int i=1; i<=n; i++) {
        f[i] = max(f[i-1]+a[i], a[i]);
        g[i] = max(g[i-1]+b[i], b[i]);
        ans1 = max(ans1, f[i]);
        ans2 = max(ans2, g[i]);
    }
    cout << max(ans1, sum+ans2);
    return 0;
}

当你提交时，你会发现：

$\color{red}WA$ 了。

$why?$

因为当所有数字为负时， $sum=-ans2$ ，所以会输出 $0$ ，而实际情况应为负数。

所以我们需要特判，当所有数字为负数时，输出 $ans1$ 。

时间复杂度： $O(n)$

$Code$

#include <iostream>
using namespace std;

const int INF = 1e9;

int n, sum, a[10010], b[10010], f[10010], g[10010], ans1 = -INF, ans1 = -INF;
bool flag;

int main() {
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> a[i];
        b[i] = -a[i];
        if (a[i] > 0) flag = true;
        sum += a[i];
    }
    for (int i=1; i<=n; i++) {
        f[i] = max(f[i-1]+a[i], a[i]);
        g[i] = max(g[i-1]+b[i], b[i]);
        ans1 = max(ans1, f[i]);
        ans2 = max(ans2, g[i]);
    }
    if (flag) cout << max(ans1, sum+ans2);
    else cout << ans1 << endl;
    return 0;
}

7 最大子矩阵和问题

朴素方法： $O(n^6)$ 、 $O(n^5)$ 、 $O(n^4)$ 不等，全是暴力，不讲。

考虑 $DP$

设 $sum_{i,j}$ 表示第 $j$ 列从第 $1$ 行到第 $i$ 行的前缀和， $b_k$ 为第 $k$ 列第 $i$ 行到第 $j$ 行的和，则有：

$b_k = sum_{k,j}-sum_{k,i-1}$ $1<=i<=j<=n,1<=k<=n$

令 $f_k$ 表示第 $k$ 列前最大的子矩阵和，则有：

$f_k=\max(f_{k-1}+b_k,b_k)$

边界： $f_0=0$

目标： $\max\{f_k\}$

$Code$

#include <iostream>
using namespace std;

int n, a[1010][1010], sum[1010][1010], b[1010], f[1010], ans = -1e9;

int main() {
    cin >> n;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++) {
            cin >> a[i][j];
            sum[j][i] = sum[j][i-1]+a[i][j];
        }
    for (int i=1; i<=n; i++)
        for (int j=i; j<=n; j++)
            for (int k=1; k<=n; k++) {
                b[k] = sum[k][j]-sum[k][i-1];
                f[k] = max(b[k], f[k-1]+b[k]);
                ans = max(ans, f[k]);
            }
    cout << ans << endl;
    return 0;    
}

例题

例题一

传送门

简化题意：求不包括 $0$ 的最大子矩阵和。

$Solution$

如果想排除掉 $0$ 的话，硬搞是很难的。

我们可以考虑将 $0$ 改成 $-\infty$ ，再套一下模板即可。

但注意，这样搞的风险就是有可能结果是负数，而现实中不可能。

所以特判一下，当 $ans$ 为负数时，输出 $0$ 即可。

时间复杂度： $O(mn^2)$

$Code$

#include <iostream>
using namespace std;

const int INF = 1e9;
long long n, m, a[1010][1010], f[1010], b[1010], ans = -INF, sum[1010][1010];

int main() {
    cin >> n >> m;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++) {
            cin >> a[i][j];
            if (a[i][j] == 0)
                a[i][j] = -INF;
            sum[j][i] = sum[j][i-1]+a[i][j];
        }
    for (int i=1; i<=n; i++)
        for (int j=i; j<=n; j++) 
            for (int k=1; k<=m; k++) {
                b[k] = sum[k][j]-sum[k][i-1];
                f[k] = max(b[k], f[k-1]+b[k]);
                ans = max(ans, f[k]);
            }
    if (ans < 0) ans = 0;
    cout << ans << endl;
    return 0;
}

8 编辑距离

不知道编辑距离的，可以看这道题目：

【问题描述】
设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：
1、删除一个字符；
2、插入一个字符；
3、将一个字符改为另一个字符。
【编程任务】
对任的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数。

$f_{i,j}$ ：将 $a$ 的前 $i$ 个字母变为 $b$ 的前 $j$ 个字母所需的最少的操作次数。

状态转移方程：

$f_{i,j}=\begin{cases}f_{i-1,j-1}&&a_i=b_j\\\min(f_{i-1,j-1},f_{i-1,j},f_{i,j-1})+1&&a_i≠b_j\end{cases}$

$f_{i-1,j-1}+1$ ：更换 $a_i$

$f_{i-1,j}+1$ ：删除 $a_i$

$f_{i,j-1}+1$ ：添加 $b_j$

边界： $f_{0,i}=f_{i,0}=i$

目标： $f_{m,n}$

$Code$

#include <iostream>
#include <string>
using namespace std;

string a, b;
int f[1010][1010], n, m;

int main() {
    cin >> a >> b;
    m = a.size(), n = b.size();
    a = ' '+a, b = ' '+b;
    for (int i=1; i<=m; i++)
        f[i][0] = i;
    for (int i=1; i<=n; i++)
        f[0][i] = i;
    for (int i=1; i<=m; i++)
        for (int j=1; j<=n; j++) {
            f[i][j] = 1e9;
            if (a[i] == b[j]) f[i][j] = f[i-1][j-1];
            else f[i][j] = min(f[i-1][j-1], min(f[i][j-1], f[i-1][j]))+1; 
        }
    cout << f[m][n] << endl;
    return 0;
}

例题

例题一

传送门

$Solution$

状态定义

根据题意，很简单，就是：

$f_{i,j}$ 表示 $A$ 串的前 $i$ 个字母与 $B$ 串的前 $j$ 个字母的最小距离。

状态转移方程

对于 $f_{i,j}$ 来说，无疑就三种情况：

$1.$ $A_i$ 与 $B_j$ 的 $ASCLL$ 码绝对值之差

$2.$ $A_i$ 对应着空格

$3.$ $B_j$ 对应着空格

显然，第一种的方程最好写： $f_{i-1,j-1}+|A_i-B_j|$

而第二种，由于 $A_i$ 对应着空格，所以，状态一定要从 $A$ 串的前 $i-1$ 个字母与 $B$ 串的前 $j$ 个字母的最小距离推得。

所以，第二个方程为： $f_{i-1,j}+k$

同理，第三个方程为： $f_{i,j-1}+k$

$f_{i,j}$ 即为三者最小值。

边界

从 $f_{i,0}$ 和 $f_{0,j}$ 入手。

先从定义出发， $f_{i,0}$ 表示 $A$ 串的前 $i$ 个字母与 $B$ 串的前 $0$ 个字母的最小距离.

是不是很怪？

所以我们只能默认第零个字母为空格，所以：

$f_{i,0}=f{i-1,0}+k$

化简一下，就是： $f_{i,0}=i*k$

同理， $f_{0,j}=j*k$

目标

设 $A$ 串长度为 $m$ , $B$ 串长度为 $n$ ，目标易求： $f_{m,n}$

$Code$

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

string a, b;
int m, n, f[2010][2010], k;

int main() {
    cin >> a >> b;
    cin >> k;
    m = a.size(), n = b.size();
    a = ' '+a, b = ' '+b;// 因为string下标从零开始，所以利用string加法的特性，开头加空格
    for (int i=1; i<=m; i++)
        f[i][0] = i*k;
    for (int j=1; j<=n; j++)
        f[0][j] = j*k;
    for (int i=1; i<=m; i++)
        for (int j=1; j<=n; j++) {
            f[i][j] = 1e9; // 因为要取最小，所以初值要赋大
            f[i][j] = min(f[i-1][j-1]+abs(a[i] - b[j]), min(f[i-1][j]+k, f[i][j-1]+k));
            //求三者最小值可用min套min
        }
    cout << f[m][n] << endl; 
    return 0; 
}

9 方格取数

不知道的戳这

$f_{i,j,k,l}$ ：第一次走到了 $(i,j)$ ，第二次走到 $(k,l)$ ，两次能取到的数字之和的最大值。

状态转移方程：

$1.f_{i,j,k,l}=\max(f_{i-1,j,k-1,l},f_{i-1,j,k,l-1},f_{i,j-1,k-1,l},f_{i,j-1,k,l-1})+a_{i,j}$

$2.if (i,j)≠(k,l)$ $f_{i,j,k,l}+=a_{k,l}$

边界： $f_{0,0,0,0}=0$

目标： $f_{n,n,n,n}$

$Code$

#include <iostream>
using namespace std;

int f[11][11][11][11], a[11][11], n;

int main() {
    cin >> n;
    int x, y, z;
    while (cin >> x >> y >> z, x && y && z) a[x][y] = z;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            for (int k=1; k<=n; k++)
                for (int l=1; l<=n; l++) {
                    f[i][j][k][l] = max(max(f[i-1][j][k-1][l], f[i-1][j][k][l-1]), max(f[i][j-1][k-1][l], f[i][j-1][k][l-1]))+a[i][j];
                    if (i != k || j != l) f[i][j][k][l] += a[k][l];
                }
    cout << f[n][n][n][n] << endl;
    return 0;
}

降维

$f_{i,j,k}$ ：两次都走了 $i$ 步，第一次走到第 $j$ 行 $(j,i-j+1)$ ，第二次走到了第 $k$ 行 $(k,i-k+1)$ ，两次能取到的数字之和的最大值。

状态转移方程：

$1.f_{i,j,k}=\max(f_{i-1,j-1,k-1},f_{i-1,j,k-1},f_{i-1,j-1,k},f_{i-1,j,k})+a_{i,i-j+1}$

$2.if(j≠k)$ $f_{i,j,k}+=a_{k,i-k+1}$

边界： $f_{0,0,0}=0$

目标： $f_{2n-1,n,n}$

$Code$

#include <iostream>
using namespace std;

int n, a[11][11], f[31][11][11];

int main() {
    cin >> n;
    int x, y, z;
    while (cin >> x >> y >> z, x && y && z) a[x][y] = z;
    for (int i=1; i<=2*n-1; i++)
        for (int j=1; j<=n; j++)
            for (int k=1; k<=n; k++) {
                f[i][j][k] = max(max(f[i-1][j-1][k-1], f[i-1][j][k-1]), max(f[i-1][j-1][k], f[i-1][j][k]));
                f[i][j][k] += a[j][i-j+1];
                if (j != k) f[i][j][k] += a[k][i-k+1];
            }
    cout << f[2*n-1][n][n] << endl;
    return 0;
}

10 乘积最大

$f_{i,j}$ ：前 $i$ 个数插入 $j$ 个乘号能得到的最大乘积

状态转移方程：

$f_{i,j}=\max\{f_{k,j-1}*num_{k+1,i}\} (j<=k<i)$

边界： $f_{i,0}=num_{1,i}$

目标： $f_{n,m}$

#include <iostream>
#include <string>
using namespace std;

int n, m, f[51][11], num[51][51];
string x;

int main() {
    cin >> n >> m;
    cin >> x;
    x = ' '+x; 
    for (int i=1; i<=n; i++)
        for (int j=i; j<=n; j++)
            num[i][j] = num[i][j-1]*10+x[j]-'0';
    for (int i=1; i<=n; i++)
        f[i][0] = num[1][i];
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
            for (int k=j; k<i; k++)
                f[i][j] = max(f[i][j], f[k][j-1]*num[k+1][i]);
    cout << f[n][m] << endl;
    return 0;
}

11杂题

$T1$

题目描述 Description
小Y最近当上了农场主！不过，还没有来得及庆祝，一件棘手的问题就摆在了小Y的面前。农场的栅栏，由于年久失修，出现了多处破损。栅栏是由n块木板组成的，每块木板可能已经损坏也可能没有损坏。小Y知道，维修连续m个木板(这m个木板不一定都是损坏的)的费用是sqrt(m)。可是，怎样设计方案才能使总费用最低呢？小Y想请你帮帮忙。

输入描述 Input Description
输入文件的第一行包含一个整数n （n<=2500），表示栅栏的长度。
第二行包含n个由空格分开的整数(长整型范围内)。如果第i个数字是0，则表示第i块木板已经损坏，否则表示没有损坏。

输出描述 Output Description
输出文件中仅包含一个实数，表示最小维修费用。注意：答案精确到小数点后3位。

样例输入 Sample Input
9
0 –1 0 1 2 3 0 –2 0

样例输出 Sample Output
3.000

$Solution$

令 $f_i$ 为修好前 $i$ 块木板的最小花费，则有

$f_i=\begin{cases}f_{i-1}&&a_i≠0\\\min\{f_{i-j}+\sqrt{j}\}&&a_i=0,1<=j<=i\end{cases}$

边界： $f_0=0,f_i=+\infty(1<=i<=n)$

目标： $f_n$

$Code$

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;

int n, a[2510];
double f[2510];

int main() {
    cin >> n;
    for (int i=1; i<=n; i++)
        cin >> a[i];
    for (int i=1; i<=n; i++)
        if (a[i] != 0)
            f[i] = f[i-1];
        else {
            f[i] = 1e9;
            for (int j=1; j<=i; j++)
                f[i] = min(f[i], f[i-j]+sqrt(j));
        }
    printf("%.3f\n", f[n]);
    return 0;
}

$T2$

题目描述 Description
聪聪的游戏全校同学都很喜欢，老师表扬了聪聪。放学回家以后，发现小表弟在家，妈妈告诉表弟：“聪聪哥哥特别会玩游戏，你让聪聪哥哥陪你玩啊！，小表弟就拿出他的积木”让聪聪陪他玩，聪聪开始不想在家陪表弟，他想和同学出去玩呢，可是妈妈说，如果陪表弟玩开心了，周末就带他去游乐场。听了这话，聪聪就跟妈妈保证，一定好好陪小表弟玩。聪聪一边拿着表弟的积木，一边在想，平常的游戏表弟都玩腻了，有什么新的好玩的呢。不一会聪聪就想到了，小表弟的这组积木有个底盘，是由很多方格组成的，积木中正好有一些与方格大小相同的正方形积木，聪聪和小表弟一起按如下规则将这些正方形积木摆放在底盘上：底盘的每一竖行方格组成一列，必须从最左边的一列开始摆放，每列从最下面的方格开始连续摆放积木，底盘至少要放两列，后一列放的积木数至少比前一列多一个。聪聪一边教表弟一边摆出不同积木数的各种情况。
这个游戏启发了聪聪，他想：如果积木底盘无限大，当积木数很多时，能摆放的情况就有很多很多，你能计算出有 N 个积木时按照上述规则能摆放出多少种情况吗？

输入描述 Input Description
一个正整数 N（N≥3），表示积木个数。

输出描述 Output Description
一个正整数，表示能摆放出的情况数。

样例输入 Sample Input
5

样例输出 Sample Output
2

数据范围及提示 Data Size & Hint
【数据范围】
对于 40%的数据满足 N≤10；
对于 80%的数据满足 N≤100；
对于 100%的数据满足 N≤200。

$Solution$

$f_{i,j}$ ：共摆放 $i$ 个积木，最后一列不超过 $j$ 个积木，的方案总数。

状态转移方程：

$f_{i,j}=\begin{cases}f_{i,j-1}&i<j\\f_{i-j,j-1}+f_{i,j-1}&i>=j\end{cases}$

边界： $f_{0,0}=1$

目标： $f_{n,n}-1$

$Code$

#include <iostream>
using namespace std;

int n, f[205][205];

int main() {
    cin >> n;
    f[0][0] = 1;
    for (int i=0; i<=n; i++)
        for (int j=1; j<=n; j++)
            if (i<j)
                f[i][j] = f[i][j-1];
            else
                f[i][j] = f[i-j][j-1]+f[i][j-1];
    cout << f[n][n]-1 << endl;
    return 0;
}

$T3$

传送门

$Solution$

对于第一个子任务，直接贪心，能取多少取多少，取满后清零再取。

对于第二个子任务，考虑 $DP$ 。

设 $f_i$ 表示前 $i$ 个教徒的最少危险值，则有：

$f_i=\min\{f_j+danger_{i,j}\}$ $(danger_{i,j}<=k)$

其中 $danger_{i,j}$ 表示 $i,j$ 之间的危险值。

问题来了： $danger_{i,j}$ 怎么求呢？

$1.$ 在跑方程的时候暴力求解。

时间复杂度： $O(n^3)$ ，显然会 $T$ 。

$2.$ 预处理。

令 $cnt$ 为计数器，当发现新的宗教时 $cnt++$ ，并且标记这个宗教，而每一段对应的 $danger_{i,j}$ 即为 $cnt$

时间复杂度： $O(n^2)$ ，可过。

至于边界，显然有 $f_0=0,f_1=1$

目标自然是 $f_n$

$Code$

(代码中的 $sum_{i,j}$ 即为 $danger_{i,j}$ )

#include <iostream>
#include <cstring>
using namespace std;

int n, m, k, a[10010], cnt, ans, sum[1010][1010], f[1010];
bool vis[10010];

int main() {
    cin >> n >> m >> k;
    for (int i=1; i<=n; i++) 
        cin >> a[i];
    for (int i=1; i<=n; i++) {
        cnt = 0;
        memset(vis, false, sizeof(vis));// 一定要清空!
        for (int j=i; j<=n; j++) {
            if (!vis[a[j]]) {
                vis[a[j]] = true;
                cnt++;
            }
            sum[i][j] = cnt;
        }
    }
    cnt = 0;
    memset(vis, false, sizeof(vis));//注意，出来时也要清空！我被坑了好长时间TAT
    for (int i=1; i<=n; i++) {
        if (!vis[a[i]]) {
            vis[a[i]] = true;
            cnt++;
        }
        if (cnt > k) {
            ans++;
            cnt = 1;
            memset(vis, false, sizeof(vis));//记得清空！
            vis[a[i]] = true;
        }
        if (i == n)
            ans++;
    }
    cout << ans << endl;
    f[0] = 0;
    f[1] = 1;//初始化莫忘掉
    for (int i=2; i<=n; i++) {
        f[i] = 1e9;//因为取最小值，所以初值要赋大
        for (int j=1; j<=i; j++) 
            if (sum[j][i] <= k) //而且危险值不能超过k
                f[i] = min(f[i], f[j-1]+sum[j][i]);
    }
    cout << f[n] << endl;
    return 0; 
}

动态规划笔记

零 动态规划的定义

一 线性DP

1 背包问题

I.01背包

01背包的降维

例题

2 最长不下降子序列（）

求出最长不下降子序列

求出降序序列的种类数

例题

例题一

例题二

例题三

例题四

3 最长公共子序列()

4 最长公共子上升子序列()

5 数塔问题

降维

求出路径

6 最大连续子数组和

优化

求数字个数

环形数组最大连续子数组和

优化

7 最大子矩阵和问题

例题

例题一

8 编辑距离

例题

例题一

9 方格取数

降维

10 乘积最大

11杂题

零动态规划的定义

一线性DP

2 最长不下降子序列（ $LIS$ ）

3 最长公共子序列( $LCS$ )

4 最长公共子上升子序列( $LCIS$ )