「Bzoj 2165」大楼 (倍增DP+矩阵快速幂)

Bzoj 2165

本题是个倍增DP，在图上做。这个图给的明显是个分层图，我们逆向运用，分层图转成一个图。
然后就可以设$dp(p,i,j)$为坐了$p$次电梯$i$到$j$能到达的最高楼层。则
$dp(p,i,j)=max(dp(p/2, i, k)+dp(p / 2, k, j))$
那么这是一个倍增DP形式，我们也可以设$2^p$的状态。
我们发现邻接矩阵自乘就是这个方程的转移，所以矩阵快速幂上就行
如果第一行有一个$\geq m$，那么不用再DP下去
然后求答案就贪心像倍增LCA那样补，同时也要一直判断第一行是否有一个$\geq m$，有就说明当前不能乘
第一行有一个$\geq m$说明当前已经到达题目要求
注意修改矩阵乘法的地方所有值都应该小于$m$

倍增DP的思想，其实ST表、LCA的pre数组求法都是这种思路。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 105;
    const LL ZINF = 2000000000000000001ll;

    int n, cnt;
    LL m;

    struct matrix {
        LL a[MAXN][MAXN];
        matrix() {for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) a[i][j] = 0;}
        void init() {for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) a[i][j] = -ZINF;}
    }f[MAXN];

    matrix mul(matrix a, matrix b) {
        matrix ret;
        ret.init();
        for (int i = 1; i <= n; ++i) 
        for (int j = 1; j <= n; ++j) 
        for (int k = 1; k <= n; ++k) ret.a[i][j] = min(m, max(ret.a[i][j], a.a[i][k] + b.a[k][j]));
        return ret;
    }
    int check(matrix a) {
        for (int i = 1; i <= n; ++i) if (a.a[1][i] >= m) return false;
        return true;
    }

    void clean() {
        cnt = 1;
    }
    int solve() {
        clean();
        scanf("%d%lld", &n, &m);
        for (int i = 1; i <= n; ++i) 
        for (int j = 1; j <= n; ++j) scanf("%lld", &f[1].a[i][j]), f[1].a[i][j] = (f[1].a[i][j] ? f[1].a[i][j] : -ZINF);
        while (1) {
            matrix tmp = mul(f[cnt], f[cnt]);
            if (check(tmp)) f[++cnt] = tmp; else break ;
        }
        LL ans = 1;
        matrix whw = f[1];
        for (int i = cnt; i > 0; --i) {
            matrix tmp = mul(whw, f[i]);
            if (check(tmp)) whw = tmp, ans += (1ll << (i - 1)); 
        }
        printf("%lld\n", ans + 1);
        return 0; 
    }
}
int main() {
    int T; scanf("%d", &T);
    while (T--) flyinthesky::solve();
    return 0;
}