SCUT_HYX SCUT_HYX 创建时间：2019-04-11 14:05 查看文章 先读读题(没读题的请回 一动点在数轴上跳，数轴上有些定点，要求求出跳过目标点最小碰到那些定点的次数。

METHOD 1. 暴力DP，首先这是题提高组的题目，有可能暴力吗，经过深思熟虑后，我们的可以以有以下思路：

对于跳到第 i i个点，我们把此时最少碰到石头的次数记为 f [ i ] f[i]，对于第 i i个点有石子， b o [ i ]

1 bo[i]=1，反之同理。

简单的得到方程 f [ i ]

m i n ( f [ i ] , f [ i − j ] ) + b o [ i ] f[i]=min(f[i],f[i−j])+bo[i] 其中 s ≤ j ≤ t s≤j≤t， s ≤ i < l + t s≤i<l+t。

但是这个小别致的时间效率实在太低辽，大概是 O ( l ) O(l)

——————————————————————————————————

METHOD 2. 在第一种方法中我们可以很容易的得出：时间效率低

那么到底低在哪里?

细细观察数据范围： L ≤ 1 0 9 L≤10 9 ， 1 ≤ M ≤ 100 1≤M≤100；

在一亿之内只有100个定点，显然有些地方是没有石头（一直都是空的数轴），在这些范围内，METHOD 1的方法浪费了很多时间。

顺着思路，我们可以很好地想到将中间没有东西的部分删掉。

楼上大佬也解释过了那我就再复读一遍：可以用2520来删去那几段没有定点的区域，因为2520是 l c m ( 1 , 2 , 3 , . . , 10 ) lcm(1,2,3,..,10)[1,2,3,..,10的最小公倍数]，所以只要每一段大于2520 * 2，就用2520削他

Q：为什么要用2520 * 2作为是否削去的根据？ A：因为如果将2520作为 ≥ ≥的界限，如果刚刚好等于的话，会被剪成同一个点，这当然就不符合现实了 ——————————————————————————————————

就是那么多了，2520缩的方法，粘下面了：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxm 104
#define maxn 2000001
using namespace std;
int l,s,t,m,ans;
int pos[maxm],f[maxn];	//f意义如上 
bool bo[maxn];			//bo[i]=1 表示在i位置有石子 
int min(int a,int b){return a<b?a:b;}
int main()
{
    scanf("%d%d%d%d",&l,&s,&t,&m);
    for(int i=1;i<=m;++i) scanf("%d",&pos[i]);
    memset(f,127,sizeof f);f[0]=0;//初始化 
	pos[m+1]=l; 		//将pos[m+1]附为l可以方便一点，后来缩的时候也要用到 
    sort(pos+1,pos+m+1);//一定要排序，因为题目中没有说是正序的
	int d=2520,dec=0;	//d就是2520，dec就是每个点要在缩前向前移的长度 
    if(s==t)			//特判s=t时
    {
        for(int i=1;i<=m;++i) if(pos[i]%s==0) ans++;
        printf("%d\n",ans);return 0;
    }
    for(int i=1;i<=m+1;++i)				//i=m+1也要被考虑，要缩最后1个石头和终点的点 
    {
        pos[i]-=dec;					//缩这条边之前先把点前移 
        while(pos[i]-pos[i-1]>d*2){pos[i]-=d; dec+=d;}//将点向前挪动d格，后面移动的数量要移dec+d格（自行理解） 
        bo[pos[i]]=1;					//这个点就有石子了 
    }
    int ans=2147483647;bo[pos[m+1]]=0;	//在pos[m+1]的位置是没有石子的，是终点，要附回来 
    for(int i=s;i<=pos[m+1]-1+t;++i)	//跳过终点也算 
        for(int j=s;j<=t;++j) 
        	if(i-j>=0) f[i]=min(f[i],f[i-j])+bo[i];//方程上面有解释QWQ 
    for(int i=pos[m+1];i<=pos[m+1]-1+t;++i) ans=min(ans,f[i]); //跳过终点也算答案的，取最小 
    printf("%d\n"); return 0;
}

____________ END ________________ 此题解代码错误