题目链接:
http://www.tyvj.cn/p/1059
题解:
当L较小时有,dp[i] = dp[i-j] + (位置i是否为石头),(dp[i] = 跳至距离为i时最少跳几个石头)
但是此题L较大,但是S,T,M较小,所以我们可以将两块较长距离的石头间的距离压缩,比如d > 200(d为两块石头间的距离)可以视作 d = 200,因为 S,T均小于10,当 d = 200 时与d > 200所能到达点的可能性相同。(不一定要取200,最小取到s*t,具体证明:http://blog.csdn.net/wdlsjdl2/article/details/51282795)。然后再注意S==T时的情况。
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<stdlib.h>
#include <string.h>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<time.h>
using namespace std;
#define MAX_N 100005
#define inf 0x3f3f3f3f
#define LL long long
#define ull unsigned long long
const LL INF = 1e18;
const int mod = 1e8+7;
typedef pair<int, int>P;
int L, S, T, M;
int dp[205*105+5];
bool st[205*105+5];
int a[105];
int main()
{
cin >> L >> S >> T >> M;
for(int i=1; i<=M; i++)
scanf("%d", &a[i]);
a[0] = 0;
a[M+1] = L;
sort(a, a+M+2);
if(S == T) {
int ans = 0;
for(int i=1; i<=M; i++)
if(a[i]%S == 0)
ans++;
cout << ans << endl;
return 0;
}
for(int i=1; i<=M+1; i++) {
if(a[i]-a[i-1]<200)
continue;
int d = a[i] - a[i-1] - 200;
for(int j=i; j<=M+1; j++) {
a[j] -= d;
}
}
memset(dp, inf, sizeof(dp));
memset(st, false, sizeof(st));
dp[0] = 0;
for(int i=1; i<=M; i++)
st[a[i]] = true;
for(int i=1; i<=a[M+1]+T; i++)
for(int j=S; j<=T; j++)
if(i-j >= 0)
dp[i] = min(dp[i], dp[i-j] + st[i]);
int ans = inf;
for(int i=a[M+1]; i<=a[M+1]+T; i++)
ans = min(ans, dp[i]);
cout << ans << endl;
return 0;
}