【动态规划】JZOJ_6311 luogu_5307 Mobitel

本文主要是介绍【动态规划】JZOJ_6311 luogu_5307 Mobitel，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给出一个$r\ast s$的矩阵，每个格子里有一个数。
每次可以向下或向右移动，求经过路径上所有数乘积不小于n的路径总数。

思路

考虑求出小于$n$的方案数

设$f_{i,j,k}$为走到点$(i,j)$，乘积为k的方案数，转移显然，时间复杂度$O(rsn)$。

优化，设$f_{i,j,k}$为走到点$(i,j)$，乘至少为k使得路径上乘积为$n-1$

发现k最多有$\sqrt{n}$个，时间复杂度$O(rs\sqrt{n})$。

代码

#include <cstdio>
#include <cstring>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)const int p = 1e9 + 7;int r, s, n, cnt;
int block[2001], rev[1000001], a[301][301], f[2][301][2001], c[301][301];int main() {//file(mobitel);scanf("%d %d %d", &r, &s, &n);n--;for (int i = 1; i <= r; i++)for (int j = 1; j <= s; j++)scanf("%d", &a[i][j]);for (int l = 1, k; l <= n; l = k + 1) {k = n / (n / l);block[++cnt] = n / l;rev[n / l] = cnt;}f[1][1][rev[n / a[1][1]]] = 1;for (int i = 1; i <= r; i++) {memset(f[(i & 1) ^ 1], 0, sizeof(f[(i & 1) ^ 1]));for (int j = 1; j <= s; j++)for (int k = 1; k <= cnt; k++) {if (i < r) (f[(i & 1) ^ 1][j][rev[block[k] / a[i + 1][j]]] += f[i & 1][j][k]) %= p;if (j < s) (f[i & 1][j + 1][rev[block[k] / a[i][j + 1]]] += f[i & 1][j][k]) %= p;}}int ans = 0;c[1][0] = 1;for (int i = 1; i <= r; i++)for (int j = 1; j <= s; j++)(c[i][j] += c[i - 1][j] + c[i][j - 1]) %= p;for (int i = 1; i <= cnt; i++)(ans += f[r & 1][s][i]) %= p;printf("%d", (c[r][s] - ans + p) % p);
}

这篇关于【动态规划】JZOJ_6311 luogu_5307 Mobitel的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---