(K. Keylogger)[https://codeforces.com/gym/103185/problem/K]

[[TOC]] 目录

tag:

  • cf分段2100
  • 动态规划，二分查找，计数，前缀差分

题意：

给定矩阵，对于矩阵第i行，每行都是上升子序列。 给定序列，求矩阵转移找满足序列的个数。

题解：

先寻找满足区间范围的数字，用的是两次二分，这样可以快速固定区间。

然后对于区间内静态查询动态修改，可以考虑使用前缀差分来加速。

最后就是滚动dp压缩空间，可以加快访问速度。

代码：


#include<bits/stdc++.h>
using namespace std;
const int  maxn = 2e3 + 7;
#define ll long long
ll x[maxn][maxn];
ll dp[2][maxn];
ll y[20000];
const int mod = 1e9 + 7;
int main() {
	ios::sync_with_stdio(0);
	ll n, k;
	cin >> n>>k;
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= n; j++) 
			cin >> x[i][j];
	int m;
	cin >> m;
	for (int j = 1; j < m; j++) 
		cin >> y[j];
	
	for (int i = 1; i <= n; i++) {
		dp[0][i] = 1;
	}
	for (int j = 1; j < m; j++) {
		//vector<int>ve(n + 2);
		int t = j & 1;
		for (int i = 1; i <= n; i++) {
			dp[t][i] = 0;
		}

		for (int i = 1; i <= n; i++) {

			auto kkk = lower_bound(x[i] + 1, x[i] + n + 1, y[j] - k) - x[i];
			auto kk = upper_bound(x[i] + 1, x[i] + n + 1, y[j] + k) - x[i];
			
			dp[t][kkk] = (dp[t][kkk] + dp[t ^ 1][i]) % mod ;
			dp[t][kk] = (dp[t][kk] - dp[t ^ 1][i] + mod) % mod;

		}
		for (int i = 1; i <= n; i++) {
			dp[t][i] = (dp[t][i] + dp[t][i - 1]) % mod;
		}
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		ans += dp[(m - 1) & 1][i];
		ans %= mod;
	}
	cout << ans << "\n";

	
}