题目链接
思路分析
#include<cstdio>
#include<cstring>
#include<algorithm>
int f[10000002];
int a[102];
int main()
{int l, s, t, m;scanf("%d%d%d%d", &l, &s, &t, &m);for (int i = 1; i <= m; i++)scanf("%d", &a[i]);a[m + 1] = l;std::sort(a + 1, a + m + 2);//石头给出的顺序不一定是升序if (s == t){int sum = 0;for (int i = 1; i <= m; i++)if (a[i] % s == 0)sum++;printf("%d\n", sum);return 0;}memset(f, 0x3f, sizeof(f));f[0] = 0;int sam = 0, p = 0;//sam存储到现在有几个f相同,p存当前是第几颗石头bool flag;for (int i = 1; i <= a[m + 1]; i++){if (sam >= t)//缩点操作{sam = 1;//t个点的f[i]一样，意味着之后到下一个点的所有中间点的结果都是一样的int d = a[p + 1] - i;for (int j = p + 1; j <= m + 1; j++)a[j] -= d;//后面每个点向前缩}flag = false;if (i == a[p + 1]){p++;flag = true;//声明当前是石头}for (int j = s; j <= t; j++)if (i - j >= 0 && f[i] > f[i - j])f[i] = f[i - j] + (flag ? 1 : 0);if (f[i] == f[i - 1])sam++;elsesam = 1;}int minn = f[a[m + 1]] - 1;//因为最后一个点被当成石头了for (int i = a[m + 1] - s; i <= a[m + 1]; i++)if (f[i] < minn)minn = f[i];printf("%d\n", minn > 0 ? minn : 0);return 0;
}