上次我们初步认识了dp
这次我们简单介绍一下几个模型
数字三角形模型
这个没有什么难度,一般都有一个特点——那就是走。
一个$npc$在一个网格里来回横跳的故事,一般都可以用这个模型解决。
举例:
摘花生
老样子。
f[i][j]
表示i
行j
列的最大值。
然后就可以写出状态转移方程了:
f[i][j] = max(f[i - 1][j], f[i][j - 1]) + a[i][j];
这道题没啥太多要注意的,就是多组样例要处理一下。
代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int T;
int n, m;
int a[N][N];
int f[N][N];
int main()
{
scanf("%d",&T);
while(T --)
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
scanf("%d", &a[i][j]);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
f[i][j] = max(f[i - 1][j], f[i][j - 1]) + a[i][j];
printf("%d\n", f[n][m]);
}
return 0;
}
注意本系列并不会带大家刷完所有题,只是挑选重点来说。
方格取数
这题是这个模型里的重难题。
先列举一下要处理的东西:
- 读入
- 走两次应该如何
dp
之状态表示 - 走两次应该如何
dp
之状态计算
首先考虑读入:
可以使用while(cin >> a >> b >> c, a || b || c)
来处理读入。
然后用同时dp
处理就行了。
那何谓同时dp
呢?
也就是说:
f[i1][j1][i2][j2]
表示第一次走到($i1$, $j1$)的位置,第二次走到($i2$, $j2$)的位置的情况。
但是....这样空间会爆炸!
所以的话我们引入一个全新的优化概念:
我愿称之为:强行压维
啥意思呢?
强行吧前两维合二为一,也就是说把第三维用于看是第一次走还是第二次走。
这是个奇怪的套路,大家最好记一下。
那么一波代码猛如虎,分分钟就带走。
#include<bits/stdc++.h>
using namespace std;
const int N = 20;
int n;
int a, b, c;
int f[N * 2][N][N];
int w[N][N];
int main()
{
cin >> n;
while(cin >> a >> b >> c, a || b || c) w[a][b] = c;
for(int k = 2; k <= 2 * n; k ++)
for(int i1 = 1; i1 <= n; i1 ++)
for(int i2 = 1; i2 <= n; i2 ++)
{
int j1 = k - i1;
int j2 = k - i2;
if(i1 >= 1 && i1 <= n && j1 >= 1 && j1 <= n)
{
int p = w[i1][j1];
if(i1 != i2) p = p + w[i2][j2];
int &x = f[k][i1][i2];
x = max(x, f[k - 1][i1 - 1][i2 - 1] + p);
x = max(x, f[k - 1][i1][i2 - 1] + p);
x = max(x, f[k - 1][i1 - 1][i2] + p);
x = max(x, f[k - 1][i1][i2] + p);
}
}
cout << f[n + n][n][n];
}
最长上升子序列模型
这个没啥。
一般都是在一个数列上加加减减玩套路,明白题意之后大胆dp
就是了。
编辑距离
这题特经典。
首先大胆设状态:
f[i][j]
表示将$a$的前$i$个字母变成$b$的前$j$个字母。
那么状态可以划分为:
- 删
- 增
- 改
然后分别考虑什么时候可以用。
删
为了不浪费次数,首先我们满足$a$的前$i - 1$项和$b$的前$j$项匹配。
这样才能完美的匹配。
所以的话问题就转化成了f[i - 1][j] + 1
是多少。
做
dp
,就想办法把目前状态的锅甩给以前的,就对了。
增
要想让增之后匹配,增加之前应该是怎样的呢?
应该是$a$的前$i$项和$b$的前$j$项匹配。
问题就转化成了:f[i][j - 1] + 1
是多少。
改
这个的话要再分。
如果$a(i) = b(j)$,变就是浪费步数,那就是f[i - 1][j - 1]
。
否则要让前面的所有字母匹配上,也就是:f[i - 1][j - 1] + 1
。
这就是本题了。
代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
int main()
{
cin >> n >> a + 1 >> m >> b + 1;
for(int i = 0; i <= m; i ++) f[0][i] = i;
for(int i = 1; i <= n; i ++) f[i][0] = i;
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
if(a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
}
}
cout << f[n][m];
}
合唱队形
因为音乐老师的强(这里读三声)迫症,我们要来做一道dp
了。
首先不难发现,本题中所求的合唱队形可以一分为二。
一部分是从前往后的LIS(最长上升子序列)。
另一部分是从后往前的LIS(最长上升子序列)。
那么可以分别预处理出以上两个数组。
接着我们枚举交汇点$k$,然后取max
即可。
原来这么水啊!
代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n, a[N], f[N], f2[N];
int main()
{
scanf("%d", &n);
int res = 0, res2 = 0;
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]), f[i] = 1, f2[i] = 1;
for(int i = 2; i <= n; i ++)
{
for(int j = 1; j < i; j ++)
{
if(a[j] < a[i]) f[i] = max(f[i], f[j] + 1), res = max(res, f[i]);
}
}
for(int i = n - 1; i >= 1; i --)
{
for(int j = n; j > i; j --)
{
if(a[i] > a[j]) f2[i] = max(f2[i], f2[j] + 1), res2 = max(res2, f2[i]);
}
}
int ans = 0;
for(int i = 1; i <= n; i ++)
{
ans = max(f[i] + f2[i], ans);
}
cout << n - ans + 1 << endl;
return 0;
}
小提示
有的时候提交dp
可能会五彩斑斓。
首先是TLE
,要不是你代码太慢, 加优化,这个下次说。
然后是MLE
,优化下空间即可压。
RE
加大一下数组。
最后是WA
,这个就是实现上的问题了,如果实现上没有问题,记得看看自己的状态转移方程对不对哦~
原来如此,强迫症原来是这样念的 qiǎng pò zhèng
没买算法课的我瑟瑟发抖
受益匪浅,orz
过奖了~
显然那张图是P的当然,哈哈哈