考试时间：16：00 - 17：30

讲解：http://www.temege.com/file/1124/2024年6月测试题目讲解.pptx

• 参考代码： -T1:

-T2:

# include <iostream>

using namespace std;
const int N = 2e3 + 5;
int f[N][N]; //从a[1- i], 到b[1  j]的编辑距离

// 相等
// f[i][j] = f[i-1][j-1]
// 修改
// f[i][j] = f[i-1][j-1] + 1
// 插入
// f[i][j] = f[i][j-1] + 1
// 删除
// f[i][j] = f[i-1][j] + 1
int main() {

	string a, b;
	cin >> a;
	cin >> b;
	for (int i = 1; i <= a.length(); i ++)
		f[i][0] = i;
	for (int j = 1; j <= b.length(); j ++)
		f[0][j] = j;
	for (int i = 1; i <= a.length(); i ++ ) {
		for (int j = 1; j <= b.length(); j ++) {
			if (a[i - 1] == b[j - 1])
				f[i][j] = f[i - 1][j - 1];
			else {
				f[i][j] = min(f[i - 1][j - 1], min(f[i][j - 1], f[i - 1][j])) + 1;
			}
		}
	}
	cout << f[a.length()][b.length()];




	return  0;
}

-T3:

//参考代码：
/*********************************************************************
    程序名: <FILENAME>
    作者: Geek+
    日期: 2024/6/14 10:05:07
    说明:
*********************************************************************/
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>


/*
解题思路：
朴素方法：
假设 f[i] 表示到达第 i 个位置最少踩到石子数
如果要到达第 i 个位置， 只能从 [i - S, i - T]
所以动态转移方程为 f[i] = min(f[j]) + flag[i];  (j >= i - S,  j <= i - T) flag[i] 表示 第i个位置是否有石子


优化方法1：压缩区间 
①观察数据范围，L较大，M比较小，说明石子都是稀疏的摆在区间[0, L] 之上
②S和T比较小， 所以可以压缩区间，
假设最大走2，最小走1， 那么可以跳跃的点为： 0 1 2 3 4 5 6，都是连续的
假设最大走4，最小走3， 那么可以跳跃的点为： 0 3 4 6 7 8 9 ，6之后都是连续的
假设最大走5，最小走4， 那么可以跳跃的点为： 0 4 5 8 9 10 12 13 14 15  ，12之后都是连续的

假设最大走10，最小走9， 那么可以跳跃的点为： 
0 9 10  18 19 20  27 28 29 30  36 37 38 39 40  45 46 47 48 49 50 
54 55 56 57 58 59 60  63 64 65 66 67 68 69 70  72 73 74 75 76 77 78 79 80  81 82 83 84 85 86 87 88 89 90 91  ，81之后都是连续的

最坏情况：最大走10，最小走9，意味着81以后都是连续的点

那么在计算  f[i] = min(f[j]) + flag[i]; 的时候， 可以把两个石子的大区间缩小至 81 以内就行，为了好计算 缩小至100 

重新处理石子之间的距离，由于石子位置不是有序的，可以先排序，然后累加每一位置偏移量，进行偏移 

优化方法2: 单调队列 


*/

using namespace std;
const int N = 1e6+10;
// 由于桥太长，可以压缩长度
int f[N];  // f[i] 表示到达第i个位置最少踩到石子的石子数
int flag[N]; //标识第i个位置是否有石子
int arr[N];
int L;
int S, T , M;
int solve(int n) {
	int offset = 0;
	// 左向偏移，假如第一个石子到第二个石子距离为500，压缩到100就行了，那就意味之后所有石子都要向右偏移400
	int last = 0;
	for(int i = 1; i <= n; i ++) {
		if(arr[i] - last >= 100) {
			offset = (offset + arr[i] - last - 100); // 计算偏移量
		}
		last = arr[i];
		arr[i] -= offset;
		flag[arr[i]] = true;
	}
	for(int i = 0; i <= arr[n]; i ++) {
		f[i] = 101;
	}
	int ans = 0;
	for(int i = S; i <= arr[n]; i ++) {
		for(int j = S; j <= T; j ++) {
			f[i]= min(f[i], f[i-j] + flag[i]);
		}
		//ans = max(ans, f[i]);
	}
	for(int i = 1; i <= T; i ++) {
		ans = max(ans, f[arr[n] - i]);
	}
	return ans;

}
int main() {


	cin >> L;
	cin >> S >> T >> M;
	for(int i = 1; i <= M; i ++) {
		cin >> arr[i];
	}
	if(S == T) {  // 特判 
		int ans = 0;
		for(int i = 1; i <= M; i ++){
			if(arr[i]%S == 0){
				ans += 1;
			}
		}
		cout << ans << endl;
	} else {
		sort(arr+1, arr + M + 1);
		f[0] = 0;
		arr[M+1] = L;
		cout << solve(M+1) << endl;
	}



	return 0;
}

-T4:

//参考代码：
/*********************************************************************
    程序名: <FILENAME>
    作者: Geek+
    日期: 2024/6/17 12:43:34
    说明:
*********************************************************************/
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>



/*
解题思路：

朴素方法：
 f[i] = min f[j] + (cnt[i] - cnt[j]) * i - (sum[i] - sum[j]));    j 在区间[0, i - m]  如果你能理解过程 j范围缩小至 [i - 2 * m, i - m] 
 
 参考过河那道题 
优化方法1： 观察数据集：时间跨度较大，但是摆渡车往返一趟时间较短 , 那么中间一些间隔就可以缩短
比如：100 - 500 这段时间，往返时间只有10 那可以压缩至 100 - 120这段时间
为什么呢？因为如果你在120时刻发车，那么上一趟必须110时刻前必须发车，可以选择 100-110之间任何区间发车
为什么不选择 100之前呢， 假设99发车，那么 100-120这个区间的人必须等到120才能发车，而这个区间还可以继续发一辆车 

所以压缩至两个往返时间即可 ， 计算偏移量，排序后重新更新出发时间 即可。 
 
优化方法2：斜率优化 

*/




using namespace std;
const int N = 1e6+10;


int n, m, last, ti; // last:最后一个人到达车站的时间
int ans = 1e9;
int cnt[N]; // 第i时刻发车的人数
int sum[N]; //第i时刻所有人到达车站的时间前缀和
int f[N];  //第i时刻发车，当前等待的最少时间

int arr[N];//每个人发车的时刻

int solve(int n, int m) {
	int maxT = 0;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &arr[i]);
		//maxT = max(maxT, arr[i]);
	}
	sort(arr+1, arr + n + 1);
	int offset = 0;
	int last = 0;
	for(int i = 1; i <= n; i ++) {
		if(arr[i] -last > 2 * m) {
			offset += (arr[i] - last - 2 * m);
		}
		last = arr[i];
		arr[i] -= offset;

	}

//	for(int i = 1; i <= n;  i ++) {
//		cout << arr[i] <<" ";
//	}

	for(int i = 1; i <= n;  i ++) {
		cnt[arr[i]]++;
		maxT = max(maxT, arr[i]);
		sum[arr[i]] += arr[i];
	}
	for (int i = 1; i < maxT + m; i++) {
		cnt[i] += cnt[i - 1];    // 数量前缀和.
		sum[i] += sum[i - 1];    // 时间前缀和
	}


	for (int i = 0; i < maxT + m; i++) {
		f[i] = cnt[i] * i - sum[i]; // 特判边界情况.
		for (int j = max(0, i - 2 * m); j <= i - m; j++) {
			f[i] = min(f[i], f[j] + (cnt[i] - cnt[j]) * i - (sum[i] - sum[j]));
		}
	}
	for (int i = maxT; i < maxT + m; i++) {
		ans = min(ans, f[i]);
	}
	return ans;
}
int main() {
	scanf("%d%d", &n, &m);  // 读入数据
	cout << solve(n, m) << endl;

}


// 朴素方法 

//int main() {
//	scanf("%d%d", &n, &m);  // 读入数据
//	for (int i = 1; i <= n; i++) {
//		scanf("%d", &ti);
//		last = max(last, ti);
//		cnt[ti]++;
//		sum[ti] += ti;
//	}
//	for (int i = 1; i < last + m; i++) {
//		cnt[i] += cnt[i - 1];    // 数量前缀和.
//		sum[i] += sum[i - 1];    // 时间前缀和
//	}
//	for (int i = 0; i < last + m; i++) {
//		f[i] = cnt[i] * i - sum[i]; // 特判边界情况.
//		for (int j = 0; j <= i - m; j++) {
//			f[i] = min(f[i], f[j] + (cnt[i] - cnt[j]) * i - (sum[i] - sum[j]));
//		}
//	}
//	for (int i = last; i < last + m; i++) {
//		ans = min(ans, f[i]);
//	}
//	printf("%d\n", ans);
//	return 0;
//}