状态转移方程:(此处是指在i处出现的石子数)
路径压缩,观察可得,由于m很小,所以石头分布的很疏,因而可以压缩中间的距离。
那么怎么压缩呢?1<=S<=T<=10,所以大于2520就压缩(1、2、3…..10的最小公倍数)
My AC Code:
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 2520*100 +5;
int l,s,t,m,dp[maxn],stone[maxn],a[105];
int min(int a,int b){return a>b?b:a;}
int main(){
scanf("%d%d%d%d",&l,&s,&t,&m);
for(int i=1;i<=m;i++)scanf("%d",&a[i]);
int ak=0;
sort(a+1,a+m+1);
for(int i=1;i<=m;i++){
if(a[i]-a[i-1]>2520)ak+=(a[i]-a[i-1])-(a[i]-a[i-1])%2520;
stone[a[i]-ak]=1;
}
for(int i=1;i<=maxn;i++)dp[i]=1<<30;
dp[0]=0;
for(int i=1;i<=maxn-5;i++)
for(int j=t;j>=s;j--)
if(i-j>=0)dp[i]=min(dp[i-j]+stone[i],dp[i]);
//当前位置若以j步跳到,则dp[i-j]+stone[i]
printf("%d",dp[maxn-5]);
return 0;
}