首页 algorithm 算法OJ 洛谷

# 守望者的逃离

P1095 NOIP 2007 普及组] 守望者的逃离 - 洛谷

很显然我们可以看出，在移动距离足够的情况下瞬移比跑步更高效

我们用 fla 变量维护当前时间瞬移的距离，用 run 变量维护当前时间跑步的距离；同时用 fla 变量维护 run 变量，即如果在某个时间点瞬移比跑步快，那么就让跑步从瞬移后的节点开始

遍历时间，看当前时间能到达的最远距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve()
{
	int m, s, t;
	cin >> m >> s >> t;
	int fla = 0, run = 0;
	for(int i = 1; i <= t; i++)
	{
		if(m >= 10) fla += 60, run += 17, m -= 10;
		else
		{
			if(fla > run) run = fla;//用 fla 更新 run
			run += 17, m += 4;  
		}
		if(max(fla, run) >= s) 
		{
			cout << "Yes" << '\n' << i;
			return;
		}
	}	
	cout << "No" << '\n' << max(fla, run);
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t = 1;
	while(t--) solve();
	return 0;
}

# 子串

P2679NOIP 2015 提高组] 子串 - 洛谷

暴力做法

首先看到字符串匹配问题，可以想到状态转移方程 f[i][j] 表示 AA 到 ii， BB 匹配到 jj

而题目要求取的子段数量不超过 kk， 所以可以将状态转移方程变成 f[i][j][p] 表示 AA 到 ii， BB 匹配到 jj，分成了 pp 段，结尾是 A[i]​ 的方案数

假设 AA 的 i - l + 1 段和 BB 的 j - l + 1 段是匹配的，那么上一次的分段点可以是 [1,i - l] 中的任何一个

因为分段点可以是 [1,i - l] ，所以，很显然就需要一个数组用来记录 f[1...i - l][j - 1][p - 1] 的和，这时就引入了 g[i][j][p]

g[i][j][p] 是 f[1...i][j][p] 的和，即所有以 A[1..i] 中任意一个字符结尾的方案数的总和。

假设 AA 和 BB 的最长公共后缀和的长度是 LL， 那么状态转移可以写成

f[i][j][p]=∑l=1L(g[i−l][j−l][p−1])f[i][j][p] = \sum_{l=1}^L(g[i- l][j - l][p - 1])

最后结果输出 g[n][m][k] 即可

因为开的数组空间太大，所以只能控制在过 70% 的数据范围，否则就会 MLE

而且时间复杂度为 O(nmk∗min(n,m))O(nmk*min(n,m)) 所以显然也会 TLE

但能过 70%，也算不错

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1000000007, N = 1001, M = 201;
int f[N][M][M], g[N][M][M];
void solve()
{
	int n, m, k;
	cin >> n >> m >> k;
	string a, b, t;
	cin >> t; a = ' ' + t;
	cin >> t; b = ' ' + t;
	for(int i = 1; i <= n; i++)
	{
		g[i - 1][0][0] = 1;
		for(int j = 1; j <= m && j <= i; j++)
		{
			for(int p = 1; p <= k && p <= m; p++)
			{
				//枚举断点
				for(int l = 1; l <= i && l <= j && a[i - l + 1] == b[j - l + 1]; l++)
				{
					f[i][j][p] = (f[i][j][p] +  g[i - l][j - l][p - 1]) % mod;
				} 
				g[i][j][p] = (g[i - 1][j][p] + f[i][j][p]) % mod;
			}
		}
	}
	cout << g[n][m][k];
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t = 1;
	while(t--) solve();
	return 0;
}

显然如果想要优化时间复杂度，需要去掉对 ll 的枚举

那么状态转移方程就可以优化成

f[i][j][p]={0a[i]!=b[j]f[i−1][j−1][p]+g[i−1][j−1][p−1]a[i]==a[j]f[i][j][p]=\left\{\begin{matrix} 0&a[i]!=b[j] \\ f[i - 1][j - 1][p] + g[i - 1][j - 1][p - 1]& a[i] == a[j] \end{matrix}\right.

时间复杂度就是 O(nmk)O(nmk) 显然可以

那么还需要优化空间复杂度

很显然 我们的 f[i]f[i] 只需要用到 f[i−1]f[i - 1] 维，所以可以参考 01 背包的优化，将第一维 ii 去掉，然后倒着遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1000000007, N = 1001, M = 201;
int f[M][M], g[M][M];
void solve()
{
	int n, m, k;
	cin >> n >> m >> k;
	string a, b, t;
	cin >> t; a = ' ' + t;
	cin >> t; b = ' ' + t;
	for(int i = 1; i <= n; i++)
	{
		g[0][0] = 1;
		for(int j = min(m, i); j >= 1; j--)
		{
			for(int p = min(k, m); p >= 1; p--)
			{
				f[j][p] = a[i] == b[j] ? (f[j - 1][p] + g[j - 1][p - 1]) % mod: 0;
				g[j][p] = (g[j][p] + f[j][p]) % mod;
			}
		}
	}
	cout << g[m][k];
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t = 1;
	while(t--) solve();
	return 0;
}

# 数字序列

P2501 HAOI2006] 数字序列 - 洛谷

题解参考

第一问：

显然如果我们直接求最长上升子序列是会产生不合法的情况的，比如： 1 2 5 3 ，直接求的最长上升子序列是 1 2 3 ，但是这个时候 5 就没有办法修改

所以我们需要让 a[j] - a[i] >= j - i

即 a[j] - j >= a[i] - 1

令 b[i] = a[i] - i ，那么就是要求 b[i] 的最长不下降子序列

第二问：

假设我们得到的 b 的最长不下降子序列是 b1 b2 b4 b9 ，那么对于 b5 ~ b8 中的 bk ，要么 bk < b5 要么 bk > b8 ；否则 bk 就会被加到最长不下降子序列中

那么我们来接着分析，怎么移动才能让变化最小呢？

分析，假设得到 b 数组 2 5 6 10 14 0 3 5 8 9

显然，对于 6 ~ 8 的这部分，把在边框外的黄色数字移到边框上，是最优解，那么移到上边框还是下边框呢？

那就看是在上边框上的多，还是下边框下的多。比如该图中显然下面的多，所以都移动到下边框，就是最优解。