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;
|
||
} |