낙곡1052

이산화+DP는 이런 문제를 처음 풀어본다. 이 문제의 DP는 어렵지 않다. F[i]는 i점에 도달했을 때 가장 적게 밟은 돌의 수를 나타낸다. F[i]=min(F[j]), i-s<=j<=i-t, i라는 위치에 돌이 있을 때 F[i]++이다. 그러나 이런 시간과 공간의 복잡도는 모두 O(n)로 감당할 수 없다. 그러나 우리는 돌의 수가 매우 작다는 것을 발견했다. 즉, n이 크면 우리는 돌이 없는 구역이 많다.그러면 우리는 이 경로를 압축할 수 있다. 어떻게 압축하는가. 한 가지 방법은 서로 인접한 두 개의 차치가 lcm(1...10)보다 큰지 판단하는 것이다. 만약에 크면 우리는 이를 본떠서 새로운 차치로 삼는다. 이렇게 하면 가장 좋은 것은 아니지만 정확성이 매우 뚜렷하다. 만약에 두 개의 차치가 lcm보다 크다면 우리는 반드시 연속적으로 k번을 뛰어서 돌에 부딪히지 않도록 한다.우리가 마지막 돌로 뛰어올랐을 때, 우리는 뒤로 t보를 뛰고, 그리고min을 취하면 답이다.

#include
#include
#include
using namespace std;
#define maxn 1005
int f[maxn*maxn],n;
int s,t,m,d[maxn];
int flag[maxn],ans=1005;
bool pd[maxn*maxn];

int main()
{
    scanf("%d",&n);
    scanf("%d%d%d",&s,&t,&m);
    for (int i=1;i<=m;i++) scanf("%d",flag+i);
    sort(flag+1,flag+m+1);
    for (int i=1;i<=m;i++) d[i]=(flag[i]-flag[i-1])%2520;
    for (int i=1;i<=m;i++) 
    {
        flag[i]=flag[i-1]+d[i];
        pd[flag[i]]=1;
    }
    memset(f,53,sizeof f);
    f[0]=0;
    for (int i=1;i<=flag[m]+t;i++) 
    {
        for (int j=s;j<=t;j++) 
        {
            if (i-j<0) break;    
            f[i]=min(f[i-j],f[i]);
        }
        if (pd[i]) f[i]++;
    }
    for (int i=0;i