经过一番努力，平平终于摘到了水果，拿近一看才发现是马蜂窝。 平平从树上掉了下来，没命的跑啊跑啊…… 后来，他发现前方有一条河。现在他用电话求助于你，希望你在他跑到之前铺好过河的路，让他顺利过河。 已知河的长度为L，现在我们有M个石子，我们可以把一个石子铺在河上的一个点，让平平踩着这些石头过河。河上已经有N个石子，而且已知平平每步跨出的距离为S到T之间的整数（ S <= T ），起点是0点，河为1到L，只要平平最后能跳过L（必须大于L）就算平平顺利过河。 如果平平能够过河，请输出最少步数，否则输出最远到达的距离，以便我们及时去救起平平。
第一行有五个整数L,N,M,S,T ，L是河的宽度，N表示河里原来就有N个石头，M表示我们手上拥有的石头，S,T表示平平的一步最小的跨度和最大跨度。接下来N行有一个值表示在河里的石头的位置（从小到大给出）。
输出仅包括一行，如果能够过河，输出最少步数，否则输出平平能够到达的最远距离。
数据规模 对于40%数据,1<=M<=L<=1000 , 1<=S<=T<=10 ; 对于100%数据,1<=M<=L<=100000; 对于100%数据,1<=S<=T<=100,1<=N<=100.
这道题明显是二维DP，那么我们有L（河的宽度），M（石子数量），N（原有石子数），又因为M<=L<=100000，所以M，L不可能作为下标
那么我们怎么才能用N表示状态？N只有100，而L有100000，由此可以见得原有石子是相当稀疏的。 我们不妨设dp[i][j]表示跳到第i颗石子，中途踩了j块原有石子的最少跳跃次数，这样也可以通过dp[i][j]-j来算出放的石子数。 有dp[i][j]=min{dp[k][j-1]+arr[k][j]}; (arr[k][j]表示从第k块石头到第j块石头需要跳多少次) 如果将L+1~L+T当做原有石头，那么答案就是min{dp[N+1~N+T][0~N+1]}了(dp[i][j]-j<=M) 如果走不到终点，不妨访问每一个有石头剩余的点，再尽量往后跳就行了。 #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; #define MAXN 220 #define MAXM 100 #define MAXL 100000 #define INF 0x3f3f3f3f typedef long long int LL; int L,N,M,S,T; int A[MAXN+10]; int arr[MAXN+10][MAXN+10]; int dp[MAXN+10][MAXM+10]; int main() { scanf("%d%d%d%d%d",&L,&N,&M,&S,&T); int i,j,k; for(i=1;i<=N;++i) scanf("%d",&A[i]); for(i=N+1;i<N+T;++i) A[i]=L+i-N; for(i=0;i<N+T;++i) for(j=i+1;j<N+T;++j) { arr[i][j]=(A[j]-A[i]+T-1)/T; if(A[j]-A[i]<S*arr[i][j]||T*arr[i][j]<A[j]-A[i]) arr[i][j]=INF; } memset(dp,0x3f,sizeof(dp)); dp[0][0]=0; for(i=1;i<N+T;++i) { for(j=1;j<=i&&j<=N+1;++j) for(k=j-1;k<i&&k<=N;++k) dp[i][j]=min(dp[i][j],dp[k][j-1]+arr[k][i]); } int ans=INF; for(i=N+1;i<N+T;++i) for(j=1;j<=N+1;++j) if(dp[i][j]-j<=M)ans=min(ans,dp[i][j]); if(ans<INF)printf("%d\n",ans); else { ans=0; for(i=1;i<=N;++i) for(j=1;j<=i;++j) if(dp[i][j]-j<=M)ans=max(ans,A[i]+(M-(dp[i][j]-j))*T); ans=max(ans,M*T); printf("%d\n",ans); } } /* 5 0 0 1 6 */