【每日一题】管道取珠
管道取珠
https://ac.nowcoder.com/acm/problem/17621
题目
题目概要：
这道题目十分的长。我就来简述一下。
有一个三叉管道，两个管子装黑白两色的球。我们已知两个管子里面球的序列。
这两个管子的球全部进入到第三个管子中，第i种小球的排列方式有
种。
种。 求
对1024523的余数。
对1024523的余数。 输入描述：
第一行包含两个整数n,m，分别表示上下两个管道中球的数目。
第二行为一个AB字符串，长度为n，表示上管道中从左到右球的类型。其中A表示浅色球，B表示深色球。
第三行为一个AB字符串，长度为m，表示下管道中的情形。
第二行为一个AB字符串，长度为n，表示上管道中从左到右球的类型。其中A表示浅色球，B表示深色球。
第三行为一个AB字符串，长度为m，表示下管道中的情形。
输出描述：
仅包含一行，即为除以1024523的余数。
除以1024523的余数。
解析
知识点
- 这道题是当然不可能是一道直接计算的题目。这道题是一道dp的题目。
看题目
- 首先我们来看题目，我们既然知道不能直接计算，那我们就要从理解这个公式的角度去写题目。
- 然后这道题目我们显然已经知道ai是啥了，但是我们现在要求ta的平方。说到平方，会想到啥？概率之积啊。
- 也就是说，我们现在可以把这道题看成是两个管道在对答案进行求解。
- 写到了dp就不得不说的话：动态规划最重要的就是递推和dp数组的含义。
算法解析
- 我们知道了怎么写之后呢，我们就要想一下，我们如果不用公式该怎么求每一种情况的答案。
- 这当然就会用到我们的动态规划dp了（数据范围也是提示）：不过这一道题要对两组管子进行dp罢了。
- 我们能想到，枚举每一种管子里面的情况，自然就有了dp[i][j][k][l]，分别表示第一组的上下管子和第二组的上下管子数目。
- 我们数据范围是500，所以我们要想办法去压缩维度，压缩空间。这里我们就发现，最多塞下两个维度。
- 所以我们找找规律，就知道这两个装置是一样的，所以我们知道了i + j = k + l。那么l维我们就不要啦，因为可以算出来。
- 接下来因为我们的递推是一直在往前走的（最后答案只要是最后一个，而且过程中不用拿来计算），所以我们不需要保存过程中的东西咯，只要前后相邻的两个用于递推就可以了。
- 那么我们就可以将第一维度换成滚动数组。
算法操作
- 首先，我们先分三层循环进行递推。分别表示三个维度。
- 第一个维度，我们用1和0表示，所以我们定义一个cur变量保存第一个数，cur ^ 1就是相对的数（1的话就是0，0的就是1）。用于表示相邻。
- 然后就是递推了：
int& last = dp[cur][j][k]; if (s1[i + 1] == s1[k + 1]) dp[cur ^ 1][j][k + 1] = (dp[cur ^ 1][j][k + 1] + last) % MOD; if (s1[i + 1] == s2[l + 1]) dp[cur ^ 1][j][k] = (dp[cur ^ 1][j][k] + last) % MOD; if (s2[j + 1] == s1[k + 1]) dp[cur][j + 1][k + 1] = (dp[cur][j + 1][k + 1] + last) % MOD; if (s2[j + 1] == s2[l + 1]) dp[cur][j + 1][k] = (dp[cur][j + 1][k] + last) % MOD; last = 0;
打代码：
- 输入变量咯。
- 然后循环dp。
- 输出最后一个。
- 看我代码趴~
AC代码
#include <iostream>
#include <string>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区
const int MOD = 1024523;
const int MAX = 507;
int n, m;
int dp[2][MAX][MAX];
string s1, s2;
//全局变量区
int main() {
IOS;
cin >> n >> m >> s1 >> s2;
s1 = " " + s1; s2 = " " + s2;
dp[0][0][0] = 1; int cur = 0;
for (int i = 0; i <= n; i++, cur ^= 1)
for (int j = 0; j <= m; j++)
for (int k = 0; k <= n; k++) {
int l = i + j - k;
int& last = dp[cur][j][k];
if (l < 0 || l > m) continue;
if (s1[i + 1] == s1[k + 1])
dp[cur ^ 1][j][k + 1] = (dp[cur ^ 1][j][k + 1] + last) % MOD;
if (s1[i + 1] == s2[l + 1])
dp[cur ^ 1][j][k] = (dp[cur ^ 1][j][k] + last) % MOD;
if (s2[j + 1] == s1[k + 1])
dp[cur][j + 1][k + 1] = (dp[cur][j + 1][k + 1] + last) % MOD;
if (s2[j + 1] == s2[l + 1])
dp[cur][j + 1][k] = (dp[cur][j + 1][k] + last) % MOD;
last = 0;
}
cout << dp[cur][m][n] << endl;
return 0;
}
//函数区每日一题 文章被收录于专栏
憨憨的专栏
