问题描述:

石头游戏在一个n行m列的方格阵上进行。每个格子对应了一个编号在0~9之间的操作序列。操作序列是一个长度不超过6且循环执行、每秒执行一个字符的字符串。它包括:
1. 数字0~9:拿0~9个石头到该格子。
2. NWSE:把这个格子内所有的石头推到相邻的格子。
3. D:拿走这个格子的石头。

石头游戏的问题是:当这个石头游戏进行了t秒之后,所有方格中最多的格子有多少个石头。

输入:

第一行三个整数n, m, t, act。
接下来n行,每行m个字符,表示每个格子对应的操作序列。
最后act行,每行一个字符串,表示从0开始的每个操作序列。

输出:

一个整数:游戏进行了t秒之后,所有方格中最多的格子有多少个石头。

思路:

这种矩阵加速递推的题重点是建模和构造矩阵。好有趣啊。。

我们可以将方格阵的两位压到一维上,那么状态矩阵$f$就是一个$1*nm$的矩阵。因为操作序列的长度不超过6,所以操作最多60次一个循环,因此我们可以对于每一次设计一个转移矩阵。然后转移矩阵$a$的构造方法是:
1. 如果位置$i,j$的操作为”WENS”,那么我们就令$a[pos(i,j)][pos(i’,j’)]=1$。其中$i’,j’$为操作的对应位置。
2. 如果位置$i,j$的操作为数字$x$,那么我们就令$a[0][pos(i,j)]=x$。
3. 另外我们要保证$a[0][0]=1$

这样我们就是把状态矩阵$f[0]$当成了石头来源,$a[0][0]=1$保证了$f[0]=1$。转移矩阵构造好以后就利用矩阵快速幂优化一下递推,这个就不多说了。主要还是构造转移矩阵,就像网络流主要是建图一样。

代码:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN 100
#define LL long long
#define pos(i, j) (i-1)*m+j
using namespace std;

int n, m, t, act, len[MAXN], op[MAXN][MAXN];
LL maxn, ans[MAXN][MAXN], a[MAXN][MAXN][MAXN], b[MAXN][MAXN];
char opt[MAXN][MAXN];

void init()
{
    ans[0][0]=1;
    for(int i=0; i<=pos(n, m); i++) b[i][i]=1;
    for(int i=0; i<60; i++) a[i][0][0]=1;
}

void mul(LL x[MAXN][MAXN], LL y[MAXN][MAXN])
{
    LL c[MAXN][MAXN];
    memset(c, 0, sizeof(c));
    for(int i=0; i<=n*m; i++)
        for(int j=0; j<=n*m; j++)
            for(int k=0; k<=n*m; k++) c[i][j]+=x[i][k]*y[k][j];
    memcpy(x, c, sizeof(c));
}

void ksm(int y)
{
    while(y)
    {
        if(y&1) mul(ans, b);
        mul(b, b); y>>=1;
    }
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &t, &act);
    init();
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) scanf("%1d", &op[i][j]);
    for(int i=0; i<act; i++)
    {
        scanf("%s", opt[i]);
        len[i]=strlen(opt[i]);
    }
    for(int k=0; k<60; k++)
    {
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
            {
                char act=opt[op[i][j]][k%len[op[i][j]]];
                if(act=='E' && j<m) a[k][pos(i, j)][pos(i, j+1)]=1;
                if(act=='N' && i>1) a[k][pos(i, j)][pos(i-1, j)]=1;
                if(act=='W' && j>1) a[k][pos(i, j)][pos(i, j-1)]=1;
                if(act=='S' && i<n) a[k][pos(i, j)][pos(i+1, j)]=1;
                if(act>='0' && act<='9')
                {
                    a[k][pos(i, j)][pos(i, j)]=1;
                    a[k][0][pos(i, j)]=act-'0';
                }
            } 
        mul(b, a[k]);
    }
    ksm(t/60);
    for(int i=0; i<t%60; i++) mul(ans, a[i]);
    for(int i=1; i<=n*m; i++) maxn=max(maxn, ans[0][i]);
    printf("%lld\n", maxn);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注