引言
今天主要刷了些 D P DP DP 问题的题目，主要是现在越是难的竞赛，比如说蓝桥杯越来越难了，那么它就越容易偏向 D P DP DP 上面靠，这类题代码非常的简单，主要是考察思维能力，而且一般现场是想不出来的，还得是之前做过同类型的题目才有可能做出来，所以得继续好好刷题了，加油！
一、最低通行费
标签：线性DP
思路：这道题看着似乎有限制，只能走 2 ∗ N − 1 2 * N - 1 2∗N−1 次，但其实最短路径也就是 2 ∗ N − 1 2 * N - 1 2∗N−1 了，也就是只能向下或者向右走，那这就非常简单了，当前状态 f [ i ] [ j ] f[i][j] f[i][j] 表示从 [ 1 , 1 ] [1,1] [1,1] 走到 [ n , n ] [n,n] [n,n] 号点所消耗的费用即， f [ i ] [ j ] = m i n ( f [ i − 1 ] [ j ] , f [ i ] [ j − 1 ] ) + w [ i ] [ j ] f[i][j] = min(f[i-1][j],f[i][j-1]) + w[i][j] f[i][j]=min(f[i−1][j],f[i][j−1])+w[i][j] 在初始化的时候把其全部变为 I N F INF INF ，然后对起点特判一下就行了，详情见代码。
题目描述：
一个商人穿过一个 N×N 的正方形的网格，去参加一个非常重要的商务活动。
他要从网格的左上角进，右下角出。
每穿越中间 1 个小方格，都要花费 1 个单位时间。
商人必须在 (2N−1) 个单位时间穿越出去。
而在经过中间的每个小方格时，都需要缴纳一定的费用。
这个商人期望在规定时间内用最少费用穿越出去。
请问至少需要多少费用？
注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。
输入格式
第一行是一个整数，表示正方形的宽度 N。
后面 N 行，每行 N 个不大于 100 的正整数，为网格上每个小方格的费用。
输出格式
输出一个整数，表示至少需要的费用。
数据范围
1≤N≤100
输入样例：
5
1 4 6 8 10
2 5 7 15 17
6 8 9 18 20
10 11 12 19 21
20 23 25 29 33
输出样例：
109
样例解释
样例中，最小值为 109=1+2+5+7+9+12+19+21+33。
示例代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 110, INF = 0x3f3f3f3f;
int n;
int w[N][N];
int f[N][N];
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= n; ++j)
{
cin >> w[i][j];
}
}
memset(f, 0x3f, sizeof f);
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= n; ++j)
{
if(i == 1 && j == 1) f[i][j] = w[i][j];
else f[i][j] = min(f[i-1][j], f[i][j-1]) + w[i][j];
}
}
cout << f[n][n] << endl;
return 0;
}
二、方格取数
标签：线性DP
思路：这道题不同的是要取两次，并且两次取到的路径是不同的，如果是一个一个取的话是不行的，因为局部最优并不代表全局最优，所以我们得同步的去走。我们可以定义一个状态 f [ k ] [ i 1 ] [ i 2 ] f[k][i1][i2] f[k][i1][i2] ，代表从起点走到 [ i 1 , k − i 1 ] , [ i 2 , k − i 2 ] ， k 代表步数 [i1,k-i1],[i2,k-i2]，k代表步数 [i1,k−i1],[i2,k−i2]，k代表步数 ，这样我们就可以同步操作了，然后就是每一个状态都可以从四个状态转移过来，分别就是向下和向右走，总共四个，由此可以推出公式： f [ k ] [ i 1 ] [ i 2 ] = m a x ( f [ k ] [ i 1 ] [ i 2 ] , f [ k − 1 ] [ i 1 − 1 ] [ i 2 − 1 ] + w [ i 1 ] [ j 1 ] ) ; f[k][i1][i2] = max(f[k][i1][i2], f[k-1][i1-1][i2-1] + w[i1][j1]); f[k][i1][i2]=max(f[k][i1][i2],f[k−1][i1−1][i2−1]+w[i1][j1]); f [ k ] [ i 1 ] [ i 2 ] = m a x ( f [ k ] [ i 1 ] [ i 2 ] , f [ k − 1 ] [ i 1 − 1 ] [ i 2 ] + w [ i 1 ] [ j 1 ] ) ; f[k][i1][i2] = max(f[k][i1][i2], f[k-1][i1-1][i2] + w[i1][j1]); f[k][i1][i2]=max(f[k][i1][i2],f[k−1][i1−1][i2]+w[i1][j1]); f [ k ] [ i 1 ] [ i 2 ] = m a x ( f [ k ] [ i 1 ] [ i 2 ] , f [ k − 1 ] [ i 1 ] [ i 2 − 1 ] + w [ i 1 ] [ j 1 ] ) ; f[k][i1][i2] = max(f[k][i1][i2], f[k-1][i1][i2-1] + w[i1][j1]); f[k][i1][i2]=max(f[k][i1][i2],f[k−1][i1][i2−1]+w[i1][j1]); f [ k ] [ i 1 ] [ i 2 ] = m a x ( f [ k ] [ i 1 ] [ i 2 ] , f [ k − 1 ] [ i 1 ] [ i 2 ] + w [ i 1 ] [ j 1 ] ) ; f[k][i1][i2] = max(f[k][i1][i2], f[k-1][i1][i2] + w[i1][j1]); f[k][i1][i2]=max(f[k][i1][i2],f[k−1][i1][i2]+w[i1][j1]);
题目描述：
设有 N×N 的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。如下图所示：
某人从图中的左上角 A 出发，可以向下行走，也可以向右行走，直到到达右下角的 B 点。
在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
此人从 A 点到 B 点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。
输入格式
第一行为一个整数N，表示 N×N 的方格图。
接下来的每行有三个整数，第一个为行号数，第二个为列号数，第三个为在该行、该列上所放的数。
行和列编号从 1 开始。
一行“0 0 0”表示结束。
输出格式
输出一个整数，表示两条路径上取得的最大的和。
数据范围
N≤10
输入样例：
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
输出样例：
67
示例代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 15;
int n;
int w[N][N];
int f[N * 2][N][N];
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
int a, b, c;
while(cin >> a >> b >> c, a || b || c) w[a][b] = c;
for(int k = 2; k <= n * 2; ++k)
{
for(int i1 = 1; i1 <= n; ++i1)
{
for(int i2 = 1; i2 <= n; ++i2)
{
int j1 = k - i1, j2 = k - i2;
if(j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n)
{
int t = w[i1][j1];
if(i1 != i2) t += w[i2][j2];
int& x = f[k][i1][i2];
x = max(x, f[k-1][i1-1][i2-1] + t);
x = max(x, f[k-1][i1-1][i2] + t);
x = max(x, f[k-1][i1][i2-1] + t);
x = max(x, f[k-1][i1][i2] + t);
}
}
}
}
cout << f[n*2][n][n] << endl;
return 0;
}
三、登山
标签：DP、线性DP、最长上升子序列
思路：其实就是从前往后找一遍最长上升子序列，再从后向前找一遍最长上升子序列，然后遍历每个点，找其之和最大的，就是所要求的结果。
题目描述：
五一到了，ACM队组织大家去登山观光，队员们发现山上一共有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景
点的编号都要大于前一个浏览景点的编号。
同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。
队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？
输入格式
第一行包含整数N，表示景点数量。
第二行包含N个整数，表示每个景点的海拔。
输出格式
输出一个整数，表示最多能浏览的景点数。
数据范围
2≤N≤1000
输入样例：
8
186 186 150 200 160 130 197 220
输出样例：
4
示例代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 1010;
int n;
int h[N];
int f1[N], f2[N];
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i) cin >> h[i];
for(int i = 1; i <= n; ++i)
{
f1[i] = 1;
for(int j = 1; j < i; ++j)
{
if(h[i] > h[j]) f1[i] = max(f1[i], f1[j]+1);
}
}
for(int i = n; i > 0; --i)
{
f2[i] = 1;
for(int j = n; j > i; --j)
{
if(h[i] > h[j]) f2[i] = max(f2[i], f2[j]+1);
}
}
int res = 0;
for(int i = 1; i <= n; ++i) res = max(res, f1[i]+f2[i]);
cout << res-1 << endl;
return 0;
}
四、友好城市
标签：DP、线性DP、最长上升子序列
思路：看着要求两个同步的最长上升子序列，由于这两个城市是一一对应的，所以直接拿一个 p a i r pair pair 来存，然后用 s o r t sort sort 排一下序，对其 s e c o n d second second 求一遍最长上升子序列就行了。
题目描述：
Palmia国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。
北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。
每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以
避免事故。
编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航线不相交的情况下，被批准的申请尽量多。
输入格式
第1行，一个整数N，表示城市数。
第2行到第n+1行，每行两个整数，中间用1个空格隔开，分别表示南岸和北岸的一对友好城市的坐标。
输出格式
仅一行，输出一个整数，表示政府所能批准的最多申请数。
数据范围
1≤N≤5000,0≤xi≤10000
输入样例：
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
输出样例：
4
示例代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 5010;
int n;
PII h[N];
int f[N];
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i)
{
int a, b; cin >> a >> b;
h[i] = {a,b};
}
sort(h+1,h+n+1);
for(int i = 1; i <= n; ++i)
{
f[i] = 1;
for(int j = 1; j < i; ++j)
{
if(h[i].y > h[j].y) f[i] = max(f[i], f[j]+1);
}
}
int res = 0;
for(int i = 1; i <= n; ++i) res = max(res, f[i]);
cout << res << endl;
return 0;
}
五、最大上升子序列和
标签：DP、线性DP、最长上升子序列
思路：其实就是把原来 f [ i ] f[i] f[i] 的值变成价值和就行了，其余的模板不变。
题目描述：
一个数的序列 bi，当 b1<b2<…<bS 的时候，我们称这个序列是上升的。
对于给定的一个序列(a1,a2,…,aN)，我们可以得到一些上升的子序列(ai1,ai2,…,aiK)，这里1≤i1<i2<…<iK≤N。
比如，对于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。
这些子序列中和最大为18，为子序列(1,3,5,9)的和。
你的任务，就是对于给定的序列，求出最大上升子序列和。
注意，最长的上升子序列的和不一定是最大的，比如序列(100,1,2,3)的最大上升子序列和为100，而最长上升子序列为(1,2,3)。
输入格式
输入的第一行是序列的长度N。
第二行给出序列中的N个整数，这些整数的取值范围都在0到10000(可能重复)。
输出格式
输出一个整数，表示最大上升子序列和。
数据范围
1≤N≤1000
输入样例：
7
1 7 3 5 9 4 8
输出样例：
18
示例代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 1010;
int n;
int w[N];
int f[N];
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i) cin >> w[i];
for(int i = 1; i <= n; ++i)
{
f[i] = w[i];
for(int j = 1; j < i; ++j)
{
if(w[i] > w[j]) f[i] = max(f[i], f[j]+w[i]);
}
}
int res = 0;
for(int i = 1; i <= n; ++i) res = max(res, f[i]);
cout << res << endl;
return 0;
}
五、拦截导弹
标签：DP、线性DP、最长上升子序列
思路：第一问直接就是模型，找最长下降子序列，把判断条件改一下即可。第二问最少有多少个最长下降子序列，我们假设有 s s s 个，那么第二个子序列中肯定有一个要大于第一个子序列中最后一个数，也就是最小的那个值，以此类推，我们可以找到一些这样的数，每个组中的一个数组成了一个最长上升子序列，因为他们两两都不在一个组里，否则就不是不升子序列了，所以第二问的解就是求一遍最长上升子序列即可。因为存在一个最长上升子序列，所以他们各自都不能放在同一个不升子序列里，所以至少要把这个最长上升子序列的数给分配完才行，所以至少需要最长不升子序列来填满一个序列的个数恰好是最长上升子序列的个数。
题目描述：
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
某天，雷达捕捉到敌国的导弹来袭。
由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少
导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
共一行，输入导弹依次飞来的高度。
输出格式
第一行包含一个整数，表示最多能拦截的导弹数。
第二行包含一个整数，表示要拦截所有导弹最少要配备的系统数。
数据范围
雷达给出的高度数据是不大于 30000 的正整数，导弹数不超过 1000。
输入样例：
389 207 155 300 299 170 158 65
输出样例：
6
2
示例代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 1010;
int n = 1;
int h[N];
int f1[N], f2[N];
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
while(cin >> h[n]) n++;
n--;
int r1 = 0, r2 = 0;
for(int i = 1; i <= n; ++i)
{
f1[i] = 1, f2[i] = 1;
for(int j = 1; j < i; ++j)
{
if(h[i] <= h[j]) f1[i] = max(f1[i], f1[j]+1);
else f2[i] = max(f2[i], f2[j]+1);
}
r1 = max(r1, f1[i]);
r2 = max(r2, f2[i]);
}
cout << r1 << endl << r2 << endl;
return 0;
}
