admin 管理员组文章数量: 887006
AcWing 206. 石头游戏(矩阵乘法加速递推 + 转移矩阵构造)
矩阵乘法加速递推的优化场景:
1.可以抽象出一个长度为n的一维向量,该向量在每个单位时间内发生一次变化.
2.变化的形式是线性递推
3.该递推式在每个时间可能作用于不同的数据上,但是数据本身不变
4.向量变化时间很长,但是向量的长度n不大
在这题中,我们发现一个操作序列的长度在1~6之间,所有数的最小公倍数就是60,也就是说,每隔60秒,所有的操作序列都会回到最开始的字符处.我们可以统计出第k秒(1<=k<=60)各个格子内执行了什么操作,然后第k + 60秒执行的操作与第k秒是完全相同的.
我们再讲所有的网格映射成一个一维的向量:
此时我们定义一行长度为n * m + 1的"状态矩阵".状态矩阵会随着时间不断变化,我们设为k秒之后的"状态矩阵".表示格子中石头的数量.初始化.此时初始状态.至于为什么这样初始化状态,我们后文会有解释.
对于1~60秒中的每一个k,我们都构造一个"转移矩阵",矩阵的行,列和下标都是0~n*m.
构造的方式如下:
1.如果网格第k秒的操作是'N', 并且i>1,令,表示把石头推到上面的格子.其他方向操作同理
2.若网格第k秒的操作是数字x,则令, ,表示本来就有的石头不动,再拿x块石头.
3.令
4.令"转移矩阵"的其他部分为0.
"转移矩阵"的主体部分是01矩阵,表示当前的状态矩阵中的某一个量在最后的"状态矩阵"中是否会出现(0消去这个量之后就不出现了,如果是1则会保留),我们可以利用01矩阵完成某个变量在位置上的转移.如果变量之前有系数呢?我们只需要在01矩阵上修改一下,把相应位置的1改成相应的系数大小即可.如果要在指定的位置加上常数项呢?我们就可以把状态矩阵的最开始的一列初始化为1,然后把转移矩阵中对应的列的最开始一行变成相应的系数,最后累加即可.
设, .
中1~n * m列中的最大值即为所求.
代码如下:
#include <bits/stdc++.h>
// #define LOCAL
#define INF 0xf3f3f3f3f3f3f3f
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
#define debug(a) cout << #a << "=" << a << endl;
using namespace std;
#define vec vector<int>
#define mat vector<vec>
const int N = 12;
int n, m, t, act;
char g[N][N], op[N][N];
int c[N][N];
int p;
mat A_, A[65], F;
int num(int i, int j){return (i - 1) * m + j;
}
/* 这里注意A的列数与B的行数相等,另外注意二维vector传参时size函数计算的大小 */
void mul(mat &A, mat &B){mat ans(A.size(), vec(B[0].size()));for (int i = 0; i < A.size(); ++i)for (int j = 0; j < B[0].size(); ++j)for (int k = 0; k < B.size(); ++k)ans[i][j] = ans[i][j] + A[i][k] * B[k][j];A = ans;
}
signed main(){
#ifdef LOCALfreopen("input.in", "r", stdin);freopen("output.out", "w", stdout);
#endifIOS;cin >> n >> m >> t >> act;for (int i = 1; i <= n; ++i){cin >> g[i] + 1;for (int j = 1; j <= m; ++j)g[i][j] -= '0';}for (int i = 0; i < act; ++i)cin >> op[i];/* 建立一个边长为n * m + 1的方阵作为转移矩阵 */p = n * m + 1;for (int i = 1; i <= 60; ++i)A[i].resize(p, vec(p));int x, y;/* 得到k=1 ~ k=60的状态矩阵 */for (int k = 1; k <= 60; ++k){for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j){x = g[i][j], y = c[i][j];if (isdigit(op[x][y])){int xx = op[x][y] - '0';A[k][0][num(i, j)] = xx;A[k][num(i, j)][num(i, j)] = 1;}else if (op[x][y] == 'N' && i > 1)A[k][num(i, j)][num(i - 1, j)] = 1;else if (op[x][y] == 'S' && i < n)A[k][num(i, j)][num(i + 1, j)] = 1;else if (op[x][y] == 'W' && j > 1)A[k][num(i, j)][num(i, j - 1)] = 1;else if (op[x][y] == 'E' && j < m)A[k][num(i, j)][num(i, j + 1)] = 1;c[i][j] = (y + 1) % strlen(op[x]);}A[k][0][0] = 1;}/* 得到A_ = A1*A2*A3*...*A60 */A_ = A[1];for (int i = 2; i <= 60; ++i)mul(A_, A[i]);/* 计算F=A_^q * F0 * A1*A2*A3*...Ar *//* 其中t=q*60+r, F0=[1,0,0,...0] */F.resize(1, vec(p));F[0][0] = 1;int w = t / 60; while (w){if (w & 1)mul(F, A_); w >>= 1;mul(A_, A_);}w = t % 60;for (int i = 1; i <= w; ++i)mul(F, A[i]); int ans = 0;for (int i = 0; i < p; ++i)ans = max(ans, F[0][i]);cout << ans << '\n';
}
本文标签： AcWing 206 石头游戏(矩阵乘法加速递推转移矩阵构造)
版权声明：本文标题：AcWing 206. 石头游戏(矩阵乘法加速递推 + 转移矩阵构造) 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732351648h1533243.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论