Atcoder-ABC291 "Teleporter and Closed off" 动态DP版

题目地址

题意：

在一个DAG图中，点 i 只有最多m条出边连向 i+1 ~ i+m（m<=10），边权均为1。对于\(k \in [2,n-1]\)，依次输出当点k被删除时1到n的最短路。

分析：

标准做法无非就是预处理1到i的最短路和i到n的最短路，又由于题目性质，对于k我们只需对[k-10,k+10]遍历一下，顺着这个思路下去就能做出来了，复杂度为\(O(nm^2)\)。

我采取了动态dp去解决这道题（动态dp可参考博客）。

思路

我们设\(dp_{\ i}\)为1到i的最短路长度。我们以m=4为例，假设点 i 仅有两条出边连向 i+1、i+4，我们处理出它的状态转移矩阵：第一行第 c 列表示i到i+c是否有边，有则值为1，否则为无穷大。于是可得状态转移方程：（注意，矩阵乘法被重新定义为 \(C_{\ i,j}=min(A_{\ i,k}+B_{\ k,j})\)，只满足结合律）

\(\begin{bmatrix}dp_{\ i}\\dp_{\ i+1}\\dp_{\ i+2}\\dp_{\ i+3}\end{bmatrix}=\begin{bmatrix}1 & \infty & \infty & 1\\0 & \infty & \infty & \infty \\\infty & 0 & \infty & \infty \\\infty & \infty & 0 & \infty \end{bmatrix}\begin{bmatrix}dp_{\ i+1}\\dp_{\ i+2}\\dp_{\ i+3}\\dp_{\ i+4}\end{bmatrix}\)

当一个点被删除时，其状态矩阵的第一行全部被替换为无穷大（之后的代码中用rep表示某点被删除后的新矩阵）。

由于每次都要获取从头到尾的dp值，所以根本不用拿线段树去维护区间矩阵乘积。我们预处理出前缀乘积和后缀乘积即可。

总复杂度为：\(O(nm^3)\)

代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod=998244353;
const int maxn = 1e5+5;
const ll inf = 1e9;
 
int n,m;
 
struct MT{
    ll mt[10][10];
}ar[maxn],pre[maxn],suf[maxn];
 
MT operator*(const MT& a,const MT& b){
    MT c;
    for(int i=0;i<m;++i)
    {
        for(int j=0;j<m;++j)
        {
            c.mt[i][j]=inf;
            for(int k=0;k<m;++k)
            {
                c.mt[i][j]=min(c.mt[i][j],a.mt[i][k]+b.mt[k][j]);
            }
        }
    }
    return c;
}
 
int main()
{
    cin.tie(0)->sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        string s;
        cin>>s;
        auto& mt=ar[i].mt;
        for(int i=0;i<m;++i)
            mt[0][i]=(s[i]=='0'? inf : 1);
        for(int i=1;i<m;++i)
            for(int j=0;j<m;++j)
                mt[i][j]=(i-1==j?0:inf);
        if(i==n)
            mt[0][0]=-inf;
    }
    MT ori,rep;
    for(int i=0;i<m;++i)
        for(int j=0;j<m;++j)
            ori.mt[i][j]=inf;
    rep=ar[1];
    for(int i=0;i<m;++i)
        rep.mt[0][i]=inf;
    
    pre[1]=ar[1];
    suf[n]=ar[n];
    for(int i=2;i<=n;++i)
        pre[i]=pre[i-1]*ar[i];
    for(int i=n-1;i>=1;--i)
        suf[i]=ar[i]*suf[i+1];
 
    for(int i=2;i<=n-1;++i)
    {
        MT res=pre[i-1]*rep*suf[i+1]*ori;
        if(res.mt[0][0]>=inf)
            cout<<"-1 ";
        else
            cout<<res.mt[0][0]<<" ";
    }
}