动态规划

人生就像动态规划一样。

我们老实人,先把课件传上来:点击下载

众所周知,老生常谈的,动态规划分为坐标型,线性型,区间型,背包型,树型,数位型等动态规划。呢就一个个谈谈吧。

坐标型

在二维的坐标系中,规定好了方向,求最值的问题,比较容易的写出动态规划方程。

最经典的问题就是,给你 $n*m$ 的格子,每个格子上有一定的权值,从左上到右下权值和最大(最小)为多少?

哎呦,上洛谷上正好找到一个非常不错的例题。

例题:P1508 Likecloud-吃、吃、吃

题目背景

问世间,青春期为何物?

答曰:“甲亢,甲亢,再甲亢;挨饿,挨饿,再挨饿!”

题目描述

正处在某一特定时期之中的李大水牛由于消化系统比较发达,最近一直处在饥饿的状态中。某日上课,正当他饿得头昏眼花之时,眼前突然闪现出了一个nm(n and m<=200)的矩型的巨型大餐桌,而自己正处在这个大餐桌的一侧的中点下边。餐桌被划分为了nm个小方格,每一个方格中都有一个圆形的巨型大餐盘,上面盛满了令李大水牛朝思暮想的食物。李大水牛已将餐桌上所有的食物按其所能提供的能量打了分(有些是负的,因为吃了要拉肚子),他决定从自己所处的位置吃到餐桌的另一侧,但他吃东西有一个习惯——只吃自己前方或左前方或右前方的盘中的食物。

由于李大水牛已饿得不想动脑了,而他又想获得最大的能量,因此,他将这个问题交给了你。

每组数据的出发点都是最后一行的中间位置的下方!

输入输出格式

输入格式:

[输入数据:]

第一行为m n.(n为奇数),李大水牛一开始在最后一行的中间的下方

接下来为m*n的数字距阵.

共有m行,每行n个数字.数字间用空格隔开.代表该格子上的盘中的食物所能提供的能量.

数字全是整数.

输出格式:

[输出数据:]

一个数,为你所找出的最大能量值.

输入输出样例

输入样例#1:

1
2
3
4
5
6
7
6 7
16 4 3 12 6 0 3
4 -5 6 7 0 0 2
6 0 -1 -2 3 6 8
5 3 4 0 0 -2 7
-1 7 4 0 7 -5 6
0 -1 3 4 12 4 2

输出样例#1:

1
41

说明

快吃!快吃!快吃!

题解

这题跟数字金字塔的做法类似。。

只不过数字金字塔是往两条路线搜索,这题是往三条路线搜。。。

动态方程: $f[i][j]=max(max(f[i-1][j],f[i-1][j-1]),f[i-1][j+1])+a[i][j]$;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
#include<cstring>
using namespace std;
int n,m,a[201][201],f[201][201]={0},x,y;
int main()
{
cin>>n>>m;
y=m/2+1;x=n;
memset(a,-9999,sizeof(a));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
f[i][j]=max(max(f[i-1][j],f[i-1][j-1]),f[i-1][j+1])+a[i][j];
//动态方程
}
}
cout<<max(max(f[x][y],f[x][y-1]),f[x][y+1])<<endl;
//因为最大值只可能在李大水牛的前方、左前方、右前方,所以只要找这三个的最大就行了
return 0;
}

引自洛谷题解。

例题:公共汽车

【问题描述】

一个城市的道路,南北向的路有n条,并由西向东从1标记到n,东西向的路有m条,并从南向北从1标记到m,每一个交叉点代表一个路口,有的路口有正在等车的乘客。一辆公共汽车将从(1,1)点驶到(n,m)点,车只能向东或者向北开.

问:司机怎么走能接到最多的乘客。

【输入】

第一行是n,m,和k,其中k是有乘客的路口的个数。以下k行是有乘客的路口的坐标和乘客的数量。已知每个路口的乘客数量不超过1000000。n,m<=1000.

【输出】

接到的最多的乘客数。

题解

$a[i,j]$ : $ (i,j)$位置的人数,

$f[i,j]​$:从(1,1)走到$(i,j)​$能接的最多人数。

$f[i,j]=max{f[i-1,j],f[i,j-1]}+a[i,j]​$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1010;
long a[maxn][maxn];

int main()
{
int n,m,k,t,s,c;
scanf("%d%d%d",&n,&m,&k);
memset(a,0,sizeof(a));
for (int i=0;i<k;i++)
{
scanf("%d%d%d",&t,&s,&c);
a[t][s]=c;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
a[i][j]+=max(a[i][j-1],a[i-1][j]);
printf("%ld",a[n][m]);
return 0;
}

线性型

目标函数为特定变量的线性函数,约束是这些变量的线性不等式(standard form)或等式(slack form),目的是求目标函数的最大值或最小值。这类动态规划是平时比较常见的一类动态规划问题。

LIS最长上升子序列

LIS (Longest Increasing Subsequence)最长上升子序列:给定n个元素的数列,求最长的上升子序列长度(LIS)。

一个数的序列$bi$,当$b1<b2<…<bSb1<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)$等等。这些子序列中最长的长度是4,比如子序列$(1,3,5,8)$。

1
2
3
4
5
6
7
8
9
10
11
8  2  7  1  9  10  1  4  3  ->  2 7 9 10
找出以每个元素为起点的所有的上升子序列:
8 9 10
2 7 9 10
7 9 10
1 9 10
9 10
10
1 4
4
3

每个数向后面比他大的点建立有向边;求最长路(顶点数最多)

由此可以得出 : $f[i]=max(f[j])+1 $$(i<j<=n$&&$a[i]<a[j])$

暴力法

当然,我们可以考虑一些暴力搜索能不能做,毕竟暴力搜索是我们做题最后得分的法宝。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;

int n,ANS;
int num[100010];

int dfs(int i)
{
int ans = 0;
for(int j = i + 1;j <= n;++j)
if(num[i] < num[j]) ans = max(ans,dfs(j));
ans++;
return ans;
}

int main(void)
{
cin >> n;

for(int i = 1;i <= n;++i)
cin >> num[i];

for(int i = 1;i <= n;++i)
ANS = max(ANS,dfs(i));

cout << ANS;

return 0;
}

显然这个暴力非常的暴力,这样做是肯定会超时的,但是我们看看搜索有没有重复的状态!?

记忆化搜索

是不是可以加个记忆化搜索呢?真棒!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;

int n,ANS;
int num[100010],dp[100010];

int dfs(int i)
{
if(dp[i] > 0) return dp[i];
for(int j = i + 1;j <= n;++j)
if(num[i] < num[j]) dp[i] = max(dp[i],dfs(j));
dp[i]++;
return dp[i];
}

int main(void)
{
cin >> n;

for(int i = 1;i <= n;++i)
cin >> num[i];

for(int i = 1;i <= n;++i)
ANS = max(ANS,dfs(i));

cout << ANS;

return 0;
}

糟糕X﹏X!!!!有没有更好的做法呢?

倒序递推求$dp[i]$

以$num[i]$为起点元素的最长上升子序列长度

每个数向后面比他大的点建立有向边;

求最长路(顶点数最多)

观察:边的顺序:$num[i]$向后的边$i+1,i+1,..,n$中选择。

可以直接倒序求即可。

$dp[n]=1​$;

$dp[i]=max(dp[j])+1 (i<j<=n​$&&$num[i]<num[j])​$

$ans=max(dp[i])$;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;

int n,ans;
int num[100010],dp[100010];

int main(void)
{
cin >> n;

for(int i = 1;i <= n;++i)
cin >> num[i];

//-------------------------------------------------
dp[n] = 1;
for(int i = n - 1;i >= 1;i--)
{
dp[i] = 0;
for(int j = i + 1;j <= n;j++)
if(num[i] < num[j]) dp[i] = max(dp[i],dp[j]);
dp[i]++;
}
//-------------------------------------------------

for(int i = 1;i <= n;++i)
ans = max(ans,dp[i]);

cout << ans;

return 0;
}

正向递推

方法当然是越少越好,所以你们自己学吧😂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;

int n,ans;
int num[100010],dp[100010];

int main(void)
{
cin >> n;

for(int i = 1;i <= n;++i)
cin >> num[i];

//-------------------------------------------------
dp[1] = 1;
for(int i = 2;i <= n;++i)
{
dp[i] = 0;
for(int j = 1;j <= i;++j)
if(num[j] < num[i]) dp[i] = max(dp[i],dp[j]);
dp[i]++;
}
//-------------------------------------------------

for(int i = 1;i <= n;++i)
ans = max(ans,dp[i]);

cout << ans;

return 0;
}

LIS变式

最长不下降序 列长度及输出改序列

合唱队列

这真的是一道好题,吹爆。

题目表述

N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2..,K,他们的身高分别为T1,T2…,Tk,则他们的身高满足T1<…Ti+1>…>Tk(1≤i≤K)。
你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。

输入输出格式

输入格式

共二行。
第一行是一个整数N(2≤N≤100),表示同学的总数。
第二行有n个整数,用空格分隔,第个整数h(130≤Ti≤230)是第同学的身高(厘米)。

输出格式

一个整数,最少需要几位同学出列。

输入输出样例

输入样例#1:

1
2
8
186 186 150 200 160 130 197 220

输出样例#1:

1
4

说明

对于50%的数据,保证有n≤20;对于全部的数据,保证有n≤100。

题解

本人觉得这题是很不错的,虽然难度不高。首先,我们要想出列最少,那么就想要留下的最多。很容易想的最长升,但是,这个序列是一个中间高,两头底的序列,最长升只能处理出单调性的序列。

那么怎么做到呢?

我们先看从T1到Ti这一段单调递增的序列,再看Ti到TK这一段单调递减的序列,那么问题就解决了。先从1到n求一趟最长升,然后从n到1也求一趟,最后枚举中间的Ti,然后从众多Ti中挑个大的。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
#include<algorithm>
using namespace std;
int a1[105][2];
int height[105];
int main(){
int n; cin>>n;
for(int i=1;i<=n;i++) cin>>height[i];
for(int i=1;i<=n;i++){//递推求最长上升子序列
a1[i][0]=1;
for(int j=1;j<i;j++){
if(height[i]>height[j]) a1[i][0]=max(a1[i][0],a1[j][0]+1);
}
}
for(int i=1;i<=n;i++){
a1[i][1]=1;
for(int j=1;j<i;j++)
if(height[i]<height[j]) a1[i][1]=max(a1[i][1],max(a1[j][0],a1[j][1] )+1);
}
int ans=0;
for(int i=1;i<=n;i++){
ans=max( ans, max( a1[i][0],a1[i][1]));
}
cout<<n-ans;
return 0;
}

摘自洛谷题解

最大上升子序列的和

把加1变为加a[i]即可。

LIS:

1
2
3
4
5
f[n]=1;

f[i]=max(f[j])+1 (i<j<=n&&a[i]<a[j])

ans=max(f[i]);

变为:

1
2
3
4
5
f[n]=a[n];

f[i]=max(f[j])+a[i] (i<j<=n&&a[i]<a[j])

ans=max(f[i]);

最大连续子序列的和

1、以$a[i]$为结束点和以$a[i-1]$为结束点的最大连续子序列和有没有联系?有什么样的联系?

2、如果事先已经求得了以$a[i-1]$为结束点的最大连续子序列和为$x$,那么怎样求以$a[i]$为结束点的最大连续子序列?

2019年6月13日

未完待续☕

本站文章除注明转载外均为原创,未经允许不要转载哇. ヾ(゚ー゚ヾ) http://chicago01.top/2019/06/11/动态规划/index.html
Compartir