【题解】LuoGu5307：[COCI2019] Mobitel

原题传送门
一个很普通的dp
$d{p}_{i,j,k}$表示第i行第j列乘积为k的路径条数
状态冗余太多，并且不优，需要优化一下
首先可以滚掉$i$这一维，接下来考虑把$k$这一维优化掉

一个定理$[\frac{[\frac{n}{x}]}{y}]=[\frac{n}{xy}]$
dp状态修改为$d{p}_{i,j,k}$表示第i行第j列，还需要乘上k才能>=n
这个k的值域是n除以所有数上取整
然后就可以愉快地dp了

Code：

#include <bits/stdc++.h>
#define maxn 310
#define maxm 2010
#define qy 1000000007
using namespace std;
int r, s, n, a[maxn][maxn], b[1000010], tot, val[maxm], pos[1000010], dp[2][maxn][maxm];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

int calc(int x, int y){ return x % y == 0 ? x / y : x / y + 1; }
void upd(int &x, int y){ if ((x += y) >= qy) x -= qy; }

int main(){
	r = read(), s = read(), n = read();
	for (int i = 1; i <= r; ++i)
		for (int j = 1; j <= s; ++j) a[i][j] = read();
	for (int i = 1; i <= n; ++i) b[i] = calc(n, i);
	for (int i = 1; i <= n; ++i)
		if (b[i] != b[i - 1]) pos[val[++tot] = b[i]] = tot;
	dp[1][1][pos[calc(n, a[1][1])]] = 1; 
	for (int i = 1; i <= r; ++i){
		int now = i & 1, nxt = now ^ 1;
		for (int j = 1; j <= s; ++j)
			for (int k = 1; k <= tot; ++k){ //printf("%dn", dp[now][j][k]);
				if (i != r) upd(dp[nxt][j][pos[calc(val[k], a[i + 1][j])]], dp[now][j][k]);
				if (j != s) upd(dp[now][j + 1][pos[calc(val[k], a[i][j + 1])]], dp[now][j][k]);
				if (i != r || j != s || k != tot) dp[now][j][k] = 0;
			}
	}
	printf("%dn", dp[r & 1][s][tot]);
	return 0;
}

最后

以上就是暴躁指甲油为你收集整理的【题解】LuoGu5307：[COCI2019] Mobitel的全部内容，希望文章能够帮你解决【题解】LuoGu5307：[COCI2019] Mobitel所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。