建站行业的发展趋势,最好看免费观看高清大全老师补课,单位门户网站怎么做,wordpress 数据表设计题目链接#xff1a;BZOJ - 2165 题目分析#xff1a; 这道题我读了题之后就想不出来怎么做#xff0c;题解也找不到#xff0c;于是就请教了黄学长#xff0c;黄学长立刻秒掉了这道题#xff0c;然后我再看他的题解才写出来。。Orz 使用 DP 倍增 #xff0c;用状态 f[…题目链接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[ab][][] 的状态转移方程是类似 Floyd 的 : f[ab][i][j] max(f[a][i][k] f[b][k][j]) 之后枚举每一个二进制位拼凑答案。如果加入这个二进制位后仍不能达到 m 就加入这一位。最后答案要加1。类似倍增求LCA 写代码过程中出现的错误:最后拼凑答案的时候用的初始矩阵不应该是全0的因为比如从 2-3 没有边但这样就增加了从 2-3 的长度为 0 的边。所以应该是对角线为 0 其余为 -INF。Orz Hzwer 找出了错误的原因 代码如下 #include iostream
#include cstdio
#include cstdlib
#include cstring
#include cmath
#include algorithmusing 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(-INF);for (int i 1; i n; i) M0.Num[i][i] 0;for (int i Top; i 0; --i) {Temp Mul(M0, M[i]);if (!Check(Temp)) {M0 Temp;Ans (1ll i);}}printf(%lld\n, Ans 1);}return 0;
}转载于:https://www.cnblogs.com/JoeFan/p/4160893.html
