GMOJ6293 迷宮

2022-09-23 02:42:10 字數 1271 閱讀 2667

為什麼這群神仙跑的這麼快。。。\(1200ms\)的我瑟瑟發抖\(qwq\)。

\(n\leq 5,m\leq 200000,q\leq 50000\)。

先想一個暴力\(dp\)怎麼做。設\(f[i][j][p][q]\)表示從第\(i\)行\(p\)列到第\(j\)行\(q\)列的最少步數。那麼對於任意一個\(k(i\leq k\leq j)\),有

\[f[i][j][p][q]=min^_(f[i][k][p][l]+f[k+1][j][l][q]+1)

\]初始化是將每一列的任意兩行的距離記錄。

顯然,這個做法是針對無修改操作的一種最暴力的區間\(dp\)。而題目是要求支援修改的,容易發現這個轉移式可以改成廣義矩陣乘法,而且每次是詢問區間的\(dp\)值,所以考慮用動態\(dp\)瞎搞。

線段樹維護區間矩陣乘法,線段樹的每一個結點\([l,r]\)儲存一個\(m\times m\)的矩陣,第\(i\)行\(j\)列表示從網格圖\(l\)行\(i\)列走到\(r\)行\(j\)列的最小路徑長度。

每次詢問時間複雜度為\(o(m^3\log n)\),總時間複雜度為\(o(nm^3+qm^3\log n)\)。

#include #include #include using namespace std;

const int n=200010,m=6,inf=1e9;

int n,m,q,opt,a[m][n];

struct matrix

friend matrix operator *(matrix a,matrix b)

void update(int x,int k)

int mid=(l[x]+r[x])>>1;

if (k<=mid) update(x*2,k);

else update(x*2+1,k);

pushup(x); }

matrix ask(int x,int ql,int qr)

}seg;

int main()

seg.build(1,1,n);

while (q--)

seg.update(1,i);

} else

}return 0;

}