首页 > 代码库 > [BZOJ 2165] 大楼 【DP + 倍增 + 二进制】
[BZOJ 2165] 大楼 【DP + 倍增 + 二进制】
题目链接:BZOJ - 2165
题目分析:
这道题我读了题之后就想不出来怎么做,题解也找不到,于是就请教了黄学长,黄学长立刻秒掉了这道题,然后我再看他的题解才写出来。。Orz
使用 DP + 倍增 ,用状态 f[x][i][j] 表示从 i 出发,坐 x 次电梯到达 j ,最多能上升的层数。开始读入的就是 f[1][][] 数组。(注意:若开始时 i 不能走到 j , 则 f[1][i][j] = -INF)
使用倍增,用 f[x][][] 求出 f[x << 1][][] , 一直求f[2^p][][], 直到出现求出的 f[][][] 数组第一行存在大于等于 m 的数值。
用 f[a][][] 和 f[b][][] 求出 f[a+b][][] 的状态转移方程是类似 Floyd 的 : f[a+b][i][j] = max(f[a][i][k] + f[b][k][j])
之后枚举每一个二进制位,拼凑答案。如果加入这个二进制位后仍不能达到 m ,就加入这一位。最后答案要加1。(类似倍增求LCA)
代码如下:
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;const int MaxN = 100 + 5;typedef long long LL;const LL INF = 1e18;int T, n, Top;LL m, Ans;struct Matrix { LL Num[MaxN][MaxN]; void Clear(LL x) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { Num[i][j] = x; } } }} M[70 + 5], M0, Temp;LL gmax(LL a, LL b) { return a > b ? a : b;}Matrix Mul(Matrix A, Matrix B) { Matrix ret; ret.Clear(-INF); for (int k = 1; k <= n; ++k) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { ret.Num[i][j] = gmax(ret.Num[i][j], A.Num[i][k] + B.Num[k][j]); if (ret.Num[i][j] > m) ret.Num[i][j] = m; } } } return ret;}bool Check(Matrix A) { for (int i = 1; i <= n; ++i) if (A.Num[1][i] >= m) return true; return false;}int main() { scanf("%d", &T); for (int Case = 1; Case <= T; ++Case) { scanf("%d%lld", &n, &m); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { scanf("%lld", &M[0].Num[i][j]); if (M[0].Num[i][j] == 0ll) M[0].Num[i][j] = -INF; } } Top = 0; while (true) { ++Top; M[Top] = Mul(M[Top - 1], M[Top - 1]); if (Check(M[Top])) break; } Ans = 0ll; M0.Clear(0); for (int i = Top; i >= 0; --i) { Temp = Mul(M[i], M0); if (!Check(Temp)) { M0 = Temp; Ans += (1ll << i); } } printf("%lld\n", Ans + 1); } return 0;}
[BZOJ 2165] 大楼 【DP + 倍增 + 二进制】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。