38 lines
1008 B
C++
38 lines
1008 B
C++
|
#include <bits/stdc++.h>
|
|||
|
|
using namespace std;
|
|||
|
|
const int N = 100500;
|
|||
|
|
int n, s, t, m; // n个长度的桥，s:起始，t:终止 m:多少个石子
|
|||
|
|
int w[N];
|
|||
|
|
const int INF = 0x3f3f3f3f;
|
|||
|
|
/*
|
|||
|
|
10
|
|||
|
|
2 3 5
|
|||
|
|
2 3 5 6 7
|
|||
|
|
*/
|
|||
|
|
int f[N]; // f[i]表示从0到i的最少石子数
|
|||
|
|
int main() {
|
|||
|
|
cin >> n;
|
|||
|
|
cin >> s >> t >> m;
|
|||
|
|
for (int i = 1; i <= m; i++) {
|
|||
|
|
int x;
|
|||
|
|
cin >> x;
|
|||
|
|
w[x] = 1; // 这个位置上有石子
|
|||
|
|
}
|
|||
|
|
// 初始化要扩展到n+t
|
|||
|
|
memset(f, 0x3f, sizeof(f));
|
|||
|
|
f[0] = 0; // 出发点需要踩0个石子
|
|||
|
|
|
|||
|
|
// 简单的DP
|
|||
|
|
for (int i = 1; i < n + t; i++)
|
|||
|
|
for (int j = i - t; j <= i - s; j++)
|
|||
|
|
// 只有在桥上的位置才需要计算石子数
|
|||
|
|
// 不建议把判断条件写在for里面，建议写在for里层，这样好理解
|
|||
|
|
if (j >= 0)
|
|||
|
|
f[i] = min(f[i], f[j] + w[i]);
|
|||
|
|
|
|||
|
|
int res = INF;
|
|||
|
|
for (int i = n; i < n + t; i++) // 从n开始，到n+t-1都是可能的终点
|
|||
|
|
res = min(res, f[i]);
|
|||
|
|
printf("%d\n", res);
|
|||
|
|
return 0;
|
|||
|
|
}
|