#include<iostream>
#include<string.h>
using namespace std;
char feet[105003];
int stone[100];
int bridge;
int small, big;
int stoneSize;
void go(){
int i, j;
for (i = bridge - big-1; i >= 0; i--){
int mm = stoneSize;
for (j = i + small; j < i + big + 1 && j < bridge; j++){
if (mm>feet[j]){
mm = feet[j];
}
}
feet[i] += mm;
}
cout << (int)feet[0] << endl;
}
void sort(int from,int to){
if (from >= to)return;
int i = from, j = to;
int k = stone[i];
while (true){
while (stone[j] > k)j--;
if (j == i)break;
stone[i] = stone[j];
stone[j] = k;
i++;
while (stone[i] < k)i++;
if (j == i)break;
stone[j] = stone[i];
stone[i] = k;
j--;
}
sort(from, i - 1);
sort(i + 1, to);
}
void cut(){
int i;
stone[0] = stone[0] % 105;
for (i = 1; i < stoneSize; i++){
stone[i] = stone[i - 1] + (stone[i]-stone[i-1])% 105;
}
}
int main(){
freopen("in.txt", "r", stdin);
cin >> bridge >> small >> big >> stoneSize;
int i;
for (i = 0; i < stoneSize; i++){
cin >> stone[i];
}
sort(0,stoneSize-1);
cut();
memset(feet, 0, sizeof(feet));
for (i = 0; i < stoneSize; i++){
feet[stone[i]] = 1;
}
bridge = stone[stoneSize - 1] + 1;
go();
return 0;
}

动态规划，奥妙无穷。
正向反向，一维二维。
状态定义，转移压缩。
常做常新的动态规划。
这道题好像只能压缩成105、210、。。。

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 500 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 492 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 468 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 532 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 508 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 500 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 500 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 524 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 520 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 468 KiB, score = 10
Accepted, time = 0 ms, mem = 532 KiB, score = 100

/*
* main.cpp
*
* Created on: 2015年1月5日
* Author: asi
*/

#include <iostream>
#include <vector>
#include <stdlib.h>
#include <fstream>

#include <string.h>

using namespace std;

#define MAXFREE 90
#define MAXVAL 101

typedef vector<int> INTVECTOR;
typedef INTVECTOR::iterator INTVCTI;

/*
* FUNCTION
* 变量的读入
*
* PARAM
* int n 桥的长度
* int s 一次跳的最短长度
* int t 一次跳的最长长度
* int m 石头的个数
* INTVECTOR var 石头的位置
*
* RETRUN
* void
*
* AUTHOR
* Asi
* VERSION
* 2015/1/5
*/
void input(int &n, int &s, int &t, int &m, INTVECTOR &var) {
int tmp;
cin >> n;
cin >> s >> t >> m;
for (int i = 0; i < m; ++i) {
cin >> tmp;
var.push_back(tmp);
}
var.push_back(0);
var.push_back(n);
}

/*
*FUNCTION
* 快排使用的比较函数
*PARAM
* const void*a 这个是读入的两个比较的数字
* const void*b
*RETURN
* int 这个输出的结果就是比较是如何排序的
*AUTHOR
* Asi
*VERSION
* 2015/01/05
*/
int cmp(const void*a, const void* b) {
int *v_a;
int v_b;
v_a = (int) a;
v_b = (int*) b;
return *v_a - *v_b;
}

/*
*FUNCTION
* 处理石子间比较大的长度，把总长度缩短
*PARAM
* INTVECTOR &var 把记录石子的数组传进来
*RETURN
* 返回的是一个int是最大的长度
*AUTHOR
* Asi
*VERSION
* 2015/01/05
*/
int funlen(INTVECTOR &var) {
INTVCTI i = var.begin();
INTVCTI j;
for (i++; i < var.end(); ++i) {
if (*i - *(i - 1) > MAXFREE) {
int t = *i - *(i - 1) - MAXFREE;
for (j = i; j < var.end(); ++j) {
*j = *j - t;
}
}
}
return var.back();
}

/*
*FUNCTION
* 输出var的内容
*PARAM
* 要输出的var
*RETURN
* void 无意义
*AUTHOR
* Asi
*VERSION
* 2015/01/05
*/
void outputvar(INTVECTOR &var) {
INTVCTI i = var.begin();
for (; i < var.end(); ++i) {
cout << *i << endl;
}
}

int main(int argc, char **argv) {
///////////////////////////////////////////
int n;
int s, t, m;
INTVECTOR var;
///////////////////////////////////////////
int len;
int* p_bridge;
int* dp;
///////////////////////////////////////////
input(n, s, t, m, var);
qsort((void*) &var[0], var.size(), sizeof(int), cmp);
///////////////////////////////////////////
if(s==t)
{
int tmp = 0;
for(INTVCTI i=var.begin()+1;i<var.end()-1;i++)
if((*i)%s==0) tmp++;
cout << tmp << endl;
return 0;
}
///////////////////////////////////////////
len = funlen(var);
p_bridge = (int*) malloc(sizeof(int) * (len + 1));
dp = (int*) malloc(sizeof(int) * (len + 1));
///////////////////////////////////////////
for (int i = 0; i <= len; i++) p_bridge[i] = 0;
for (INTVCTI i = var.begin() + 1; i < var.end() - 1; ++i) p_bridge[*i] = 1;
for (int i = 0; i <= len; i++) dp[i] = MAXVAL;
dp[0] = 0;
///////////////////////////////////////////
for (int i = 1; i < len + 1; ++i) {
for (int j = i - t; j <= i - s; ++j) {
if (j >= 0) {
dp[i] = min(dp[j] + p_bridge[i], dp[i]);
}
}
}
///////////////////////////////////////////
cout << dp[len] << endl;
free(dp);
dp = NULL;
free(p_bridge);
p_bridge = NULL;
return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=110;
const int maxdp=100001;
const int inf=100000000;
const int ya=100;
int len,s,t,n;
int cnt=0;
int a[maxn],dp[maxdp],v[maxdp];
int cmp(int x,int y)
{
return x<y;
}
int main()
{
cin>>len>>s>>t>>n;
for(int i=1;i<=n;i++) cin>>a[i];
a[n+1]=len; a[0]=0;
if(s==t)
{
for(int i=1;i<=n;i++)
if(a[i]%s==0) cnt++;
cout<<cnt;
return 0;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n+1;i++)
if(a[i]-a[i-1]>ya)
{
int t=a[i]-a[i-1]-ya;
for(int j=i;j<=n+1;j++) a[j]=a[j]-t;
}
memset(v,0,sizeof(v));
for(int i=1;i<=n;i++) v[a[i]]=1;
len=a[n+1];
for(int i=0;i<maxdp;i++) dp[i]=inf;
dp[0]=0;
for(int i=1;i<=len;i++)
for(int j=i-t;j<=i-s;j++)
if(j>=0)
dp[i]=min(dp[i],dp[j]+v[i]);
cout<<dp[len];
return 0;
}

#include<cstdio>
#include<cstring>
#include<algorithm>

inline void update(int &a,int b)
{
a=a<b?a:b;
}

int main()
{
int L,S,T,M,f[10],stone[100],ans=0x3f3f3f3f;
scanf("%d%d%d%d",&L,&S,&T,&M);
for(int i=0;i<M;i++)
scanf("%d",stone+i);
if (S==T)
{
ans=0;
for(int i=0;i<M;i++)
if (stone[i]%T==0) ans++;
printf("%d",ans);
return 0;
}
std::sort(stone,stone+M);
memset(f,0x3f,sizeof(f));
f[0]=0;
for(int i=0,now=0,tot=0,pos=0;i<=L+T;i++)
{
for(int j=S;j<=T;j++)
update(f[i%T],f[(i-j+T)%T]);
if (stone[pos]==i)
{
f[i%T]++;
pos++;
}
if (now==f[i%T]) tot++;
else
{
now=f[i%T];
tot=0;
}
if (tot==T)
i=(stone[pos]-T)/T*T;
}
for(int i=0;i<T;i++)
update(ans,f[i]);
printf("%d",ans);
return 0;
}

var
i,s,t,n,min,l,p,j,d:longint;
f:array[0..10]of integer;
shi:array[1..105]of longint;
function same:boolean;
var
i:integer;
begin
for i:=1 to t do
if f[i]<>f[i-1] then
exit(false);
exit(true);
end;
procedure qst(i,j:integer);
var
ii,jj,xx:longint;
begin
ii:=i;
jj:=j;
xx:=shi[ii];
repeat
while (ii<jj) and (shi[jj]>=xx) do
dec(jj);
shi[ii]:=shi[jj];
while (ii<jj) and (shi[ii]<=xx) do
inc(ii);
shi[jj]:=shi[ii];
until ii=jj;
shi[ii]:=xx;
if i<ii-1 then
qst(i,ii-1);
if ii+1<j then
qst(ii+1,j);
end;
begin
fillchar(f,sizeof(f),1);
f[0]:=0;
readln(l);
readln(s,t,n);
for i:=1 to n do
read(shi[i]);
if s=t then
begin
for i:=1 to n do
if shi[i] mod s=0 then
min:=min+1;
write(min);
exit;
end;
qst(1,n);
p:=1;

for i:=s to t do
if shi[p]=i then
begin
if f[i mod (t+1)]=1 then
p:=p+1;
end
else
f[i mod (t+1)]:=0;
while i<=shi[p] do
begin
repeat
d:=0;
if shi[p]=i then
begin
d:=1;
p:=p+1;
end;
f[i mod(t+1)]:=257;
for j:=s to t do
if f[i mod(t+1)]> f[(i-j+t+1)mod(t+1)]+d then
f[i mod(t+1)]:=f[(i-j+t+1)mod(t+1)]+d;
i:=i+1;
if i>=l then
break;
until same;
if p<n then
i:=shi[p]
else
break;
end;
min:=257;
for i:=l to l+t-1 do
for j:=s to t do
if f[(i-j+t+1)mod(t+1)]<f[i mod(t+1)] then
f[i mod(t+1)]:= f[(i-j+t+1)mod(t+1)] ;
for i:=l to l+t-1 do
if f[i mod (t+1)]< min then
min:=f[i mod (t+1)];
writeln(min);
end.

压缩路径.
.
.
.
.

测试数据 #0: Accepted, time = 0 ms, mem = 1840 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1840 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 1840 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1840 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 1840 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1836 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 1844 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 1840 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1844 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 1840 KiB, score = 10
Accepted, time = 45 ms, mem = 1844 KiB, score = 100

var
a,p,q,r,i,j,l,s,t,m:longint;
b,c,po:array[1..100000]of longint;
begin
fillchar(b,sizeof(b),1000000);fillchar(c,sizeof(c),0);fillchar(po,sizeof(po),0);
readln(l);readln(s,t,m);
for i:=1 to m do begin read(a);po[a]:=1;end;
r:=0;
repeat
for i:=r+s to r+t do begin
for j:=s to t do
if b[i-j]+po[i]<b[i] then b[i]:=b[i-j]+po[i]
end;
r:=r+t-s+1;
until r>l;
writeln(b[l]);
end.

#include <cstdio>
#include <cstring>
#include <algorithm>
#define REP( i, n ) for ( int i = 1; i <= n; i ++ )
#define FOR( i, a, b ) for ( int i = a; i <= b; i ++ )
#define DWN( i, a, b ) for ( int i = b; i >= a; i -- )
#define RST( a, x ) memset ( a, x, sizeof ( a ) );
#define NSIZE 200
#define LSIZE 100000
#define ONLINE_JUDGE NULL

using namespace std;
int s, t, l, n, ans = ( 1 << 30 );
int pos[ NSIZE ], dp[ LSIZE ];
bool st[ LSIZE ];
int main ()
{

#ifndef ONLINE_JUDGE
freopen ( "P1002.in", "r", stdin );
freopen ( "P1002.out", "w", stdout );
#endif

RST ( dp, 40 );
scanf ( "%d%d%d%d", &l, &s, &t, &n );
REP ( i, n ) scanf ( "%d", &pos[ i ] );
pos[ n + 1 ] = l;
sort ( pos + 1, pos + n + 1 );
REP ( i, n + 1 )
{
if ( s == t )
{
if ( ( pos[ i ] - pos[ i - 1 ] ) % s == 0 ) pos[ i ] = pos[ i - 1 ] + s;
else pos[ i ] = pos[ i - 1 ] + ( pos[ i ] - pos[ i - 1 ] ) % s;
}
else if ( pos[ i ] - pos[ i - 1 ] > 600 ) pos[ i ] = pos[ i - 1 ] + ( pos[ i ] - pos[ i - 1 ] ) % 600;
if ( i <= n ) st[ pos[ i ] ] = true;
}
dp[ 0 ] = 0;
l = pos[ n + 1 ];
FOR ( i, s, l + 20 )
{
FOR ( j, s, t )
dp[ i ] = min ( dp[ i ], dp[ i - j ] + st[ i ] );
if ( i >= l ) ans = min ( ans, dp[ i ] );
}
printf ( "%d\n", ans );
return 0;
}
我和很多人第一次敲代码都非常长……其实一点必要都没有……感觉缩到40行也可以……
……第一次发的时候格式错了……我这个强迫症患者……

我和很多人第一次敲代码都非常长……其实一点必要都没有……
#include <cstdio>
#include <cstring>
#include <algorithm>
#define REP( i, n ) for ( int i = 1; i <= n; i ++ )
#define FOR( i, a, b ) for ( int i = a; i <= b; i ++ )
#define DWN( i, a, b ) for ( int i = b; i >= a; i -- )
#define RST( a, x ) memset ( a, x, sizeof ( a ) );
#define NSIZE 200
#define LSIZE 100000
#define ONLINE_JUDGE NULL

using namespace std;
int s, t, l, n, ans = ( 1 << 30 );
int pos[ NSIZE ], dp[ LSIZE ];
bool st[ LSIZE ];
int main ()
{

#ifndef ONLINE_JUDGE
freopen ( "P1002.in", "r", stdin );
freopen ( "P1002.out", "w", stdout );
#endif

RST ( dp, 40 );
scanf ( "%d%d%d%d", &l, &s, &t, &n );
REP ( i, n ) scanf ( "%d", &pos[ i ] );
pos[ n + 1 ] = l;
sort ( pos + 1, pos + n + 1 );
REP ( i, n + 1 )
{
if ( s == t )
{
if ( ( pos[ i ] - pos[ i - 1 ] ) % s == 0 ) pos[ i ] = pos[ i - 1 ] + s;
else pos[ i ] = pos[ i - 1 ] + ( pos[ i ] - pos[ i - 1 ] ) % s;
}
else if ( pos[ i ] - pos[ i - 1 ] > 600 ) pos[ i ] = pos[ i - 1 ] + ( pos[ i ] - pos[ i - 1 ] ) % 600;
if ( i <= n ) st[ pos[ i ] ] = true;
}
dp[ 0 ] = 0;
l = pos[ n + 1 ];
FOR ( i, s, l + 20 )
{
FOR ( j, s, t )
dp[ i ] = min ( dp[ i ], dp[ i - j ] + st[ i ] );
if ( i >= l ) ans = min ( ans, dp[ i ] );
}
printf ( "%d\n", ans );
return 0;
}

输入的数据是无序的,记得排序，冒泡就行了

Const
maxl=maxlongint div 3;

Var
l,s,t,n,len:Longint;
f:array[1..10000000]of longint;
a:array[1..101]of longint;

Procedure print;
var
i,j,k:longint;
begin
k:=0;
for i:=1 to n do
if a[i] mod s=0 then inc(k);
writeln(k);
halt;
end;

Procedure Qsort(l,r: longint);
var
i,j,x,y: longint;
begin
i:=l;j:=r;
x:=a[(l+r) div 2];
repeat
while a[i]<x do inc(i);
while x<a[j] do dec(j);
if not(i>j) then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
inc(i); dec(j);
end;
until i>j;
if l<j then Qsort(l,j);
if i<r then Qsort(i,r);
end;

Procedure init;
var
i,j,k,tot,p:longint;
begin
readln(l);
readln(s,t,n);
for i:=1 to n do
read(a[i]);
Qsort(1,n);
inc(n);
a[n]:=l;
if s=t then print;
p:=2*t;len:=0;tot:=0;
for i:=1 to n do
begin
dec(a[i],tot);
if p+t+1<a[i] then
begin
len:=p+t+1;
inc(tot,a[i]-len);
f[len]:=1;
end else
begin
len:=a[i];
f[len]:=1;
end;
p:=len;
end;
end;

Procedure work;
var
i,j,k,ans:longint;
dp:array[1..1000000]of longint;
begin
for i:=1 to len+t+1 do
dp[i]:=maxl;
for i:=s to t do
dp[i]:=f[i];
for i:=t+1 to len+t+1 do
for j:=i-t to i-s do
if dp[j]+f[i]<dp[i] then
dp[i]:=dp[j]+f[i];
ans:=maxl;
for i:=len to len+t+1 do
if dp[i]<ans then ans:=dp[i];
writeln(ans);
end;

Begin
init;
work;
End.

这道题是NOIP第一道DP优化题，看似容易，实际上想要满分也颇有难度。
###算法
此题显然要用到DP，DP方程也显而易见：
if (stone[i]) f[i]=min{f[i-j]}+1; (S<=j<=T)
else f[i]=min{f[i-j]};
这样的时间复杂度为 O(LT) ，空间复杂度为 O(L) 。
而此题的L高达 10亿 ，所以这种朴素的方法只能得 30分 ，显然无法AC。
###优化
1.滚动数组
根据我们得出的DP方程，状态转移只需用到 f[i-T]~f[i-S] 的值，所以只需开大小为T的滚动数组即可。
所以空间复杂度被优化到了 O(T) 。由于T小于等于10，所以空间上显然没有问题。
2.离散化DP
看了看别人的题解，发现有人选择压105位来优化，这种方法虽然能过，但是或多或少有投机取巧的嫌疑，毕竟比赛时谁知道去压正好105位呢？
所以我们必须想出一般性的方法。我们会发现，石头的个数M远远小于长度L，不禁让我们想到了离散化——当S<T且有一大段桥没有石头时，常常会出现整个滚动数组f的值一样的情况，这时我们可以在遇到下一颗石头之前不再改变f的值，从而达到优化的效果。
在下用tot变量记录当前数值连续出现的次数，如果超过T次，则将i直接跳转到下一个石头的位置之前，从而提高效率。
优化后，时间复杂度降至 O(MT) ，已经达到了AC的要求。
###特判
上面的离散化显然建立在S<T的基础上。如果S==T，那么永远达不到优化的条件，优化就不会奏效，从而 **TLE：90分 ** 。
因此我们必须加上特判，当S==T时，ans就是位置为T的倍数的石头的数量。虽然简单，却十分考验选手思维的严密性。
###标程

#include <cstdio>
#include <cstring>
#include <climits>

inline int min(int a,int b)
{
return a<b?a:b;
}

int f[20],a[200],L,S,T,M,i,j,p,c,ans=INT_MAX,now,tot;

int main()
{
scanf("%d%d%d%d",&L,&S,&T,&M);
for (i=0;i<M;i++)
scanf("%d",&a[i]);
if (S==T)
{
ans=0;
for (i=0;i<M;i++)
if (a[i]%T==0)
ans++;
printf("%d",ans);
return 0;
}
for (i=0;i<M-1;i++)
for (j=i+1;j<M;j++)
{
if (a[i]>a[j])
{
c=a[i];
a[i]=a[j];
a[j]=c;
}
}
memset(f,0x7F,sizeof(f));
f[0]=0; now=0; tot=0;
for (i=1;i<L+T;i++)
{
for (j=S;j<=T;j++)
{
f[i%T]=min(f[i%T],f[(i-j+T)%T]);
}
if (a[p]==i)
{
f[i%T]++;
p++;
}
if (now==f[i%T])
{
tot++;
}
else
{
now=f[i%T];
tot=0;
}
if (tot==T)
{
i+=(min(a[p]-T,L)-i)/T*T;
}
}
for (i=0;i<T;i++)
{
ans=min(ans,f[i]);
}
printf("%d\n",ans);
return 0;
}

题解

青蛙终于过河了
昨晚睡觉时突然想起需要特判的情况，就是S=T的时候，直接判断每个石子位置mod s是否为0.
其余情况要考虑有些位置根本不可能踩到，不仅仅包括(1,s-1)
最后就是要压缩了。。

我提交了N次
分数变化
0-0-0-70-60-80-0-0

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 2416 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 2424 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 2428 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 2420 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 2416 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 2424 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 2420 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 2420 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 2420 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 2420 KiB, score = 10
Accepted, time = 0 ms, mem = 2428 KiB, score = 100

六次提交，三次re，的，蛋疼死
贴个程序

#include<cstdio>
#include<algorithm>
using namespace std;
int f[252010],a[110],x[110],c[252010];
int m,l,s,t;
int gcd(int a,int b)
{
if (b==0) return a;
return gcd(b,a%b);
}
int main()
{
freopen("1002.in","r",stdin);
freopen("1002.out","w",stdout);
scanf("%d",&l);
scanf("%d%d%d",&s,&t,&m);
for(int i=1;i<=m;i++) scanf("%d",&a[i]);
sort(a+1,a+m+1);
for(int i=1;i<=m;i++)
{
if (i==1) x[0]=a[i];
else x[i-1]=a[i]-a[i-1];
}
x[m]=l-a[m];
int ss=1;
for (int i=s;i<=t;i++)
{
int z=gcd(ss,i);
ss*=(i/z);
}
for(int i=0;i<=m;i++)
if (x[i]>ss) x[i]=x[i]%ss+ss;
int start=0;
for(int i=0;i<m;i++)
{
start+=x[i];
a[i+1]=start;
c[a[i+1]]++;
}
l=start+x[m];
for(int i=1;i<=l;i++) f[i]=23333333;
f[0]=0;
for(int i=1;i<=l;i++)
for (int j=s;j<=t;j++)
if (i>=j)
if (f[i-j]+c[i]<f[i]) f[i]=f[i-j]+c[i];
for(int i=l;i>=1;i--)
if (f[i]!=23333333)
{
printf("%d",f[i]);
break;
}
return 0;
}

题解：http://blog.163.com/syf_light_feather/blog/static/22375506720136288737938/?latestBlog

我压100，AC，压75，AC，压10，竟然也AC。实在搞不懂其中的数学原理。求高手讲解。