洛谷P1052 过河
通过观察可以发现
这个点很稀疏
dp 有很长一段距离都是没有用的，那么我们可以采用离散化的思想
把这个距离压缩，但同时还要保证 对答案没有影响
如果 s==t 这时候我们需要特判 只要判断 pos[ i ] % s == 0 就可以知道是否踩到石子
然后因为 最多青蛙一次只跳了 10
假如 s == 9 t == 10 如果两个石子间的距离大于100 我们每次也可以 一步步的慢慢调整 ，其实总共只有
10个状态，%10==1 %10==2 %10==3 然后我们就可以把距离 > 100 的距离变成 100
这样就将距离压缩
时间复杂度 m*100*(t-s)
1 #include <bits/stdc++.h> 2 #define For(i,j,k) for(int i=j;i<=k;i++) 3 using namespace std ; 4 5 const int N = 100011,inf = 1e9 ; 6 int L,s,t,m,pos[111],d[111],dp[N],a[N] ; 7 8 inline int read() 9 { 10 int x = 0 , f = 1 ; 11 char ch = getchar() ; 12 while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; } 13 while(ch>='0'&&ch<='9') { x = x * 10+ch-48 ; ch = getchar() ; } 14 return x * f ; 15 } 16 17 int main() 18 { 19 L = read() ; 20 s = read() ; t = read() ; m = read() ; 21 For(i,1,m) pos[ i ] = read() ; 22 if(s==t) { 23 int sum = 0 ; 24 For(i,1,m) if(pos[ i ]%s==0) sum++ ; 25 printf("%d ",sum) ; 26 return 0 ; 27 } 28 pos[++m] = L ; 29 pos[++m] = 0 ; // 起点 终点 之间的距离也要压缩 30 sort(pos+1,pos+m+1) ; 31 For(i,1,m-1) { 32 d[ i ] = pos[i+1] - pos[i] ; 33 if( d[i]>100 ) d[i] = 100 ; 34 } 35 For(i,2,m) pos[ i ] = pos[i-1] + d[i-1] ; 36 L = pos[ m ] ; 37 m-- ; 38 For(i,2,m) a[ pos[ i ] ] = 1 ; 39 dp[ 0 ] = 0 ; 40 For(i,1,L) dp[ i ] = inf ; 41 For(i,1,L) 42 For(d,s,t) { 43 if( i-d<0 ) break ; 44 dp[ i ] = min(dp[ i ],dp[ i-d ]+a[ i ]) ; 45 } 46 printf("%d ",dp[ L ]) ; 47 return 0 ; 48 }