tyvj 1059 過河 dp

P1059 過河

時間: 1000ms / 空間: 131072KiB / Java類名: Main

背景

NOIP2005?提高組?第二道

描述

在河上有一座獨木橋，一只青蛙想沿著獨木橋從河的一側跳到另一側。在橋上有一些石子，青蛙很討厭踩在這些石子上。由于橋的長度和青蛙一次跳過的距離都 是正整數，我們可以把獨木橋上青蛙可能到達的點看成數軸上的一串整點：0，1，……，L（其中L是橋的長度）。坐標為0的點表示橋的起點，坐標為L的點表 示橋的終點。青蛙從橋的起點開始，不停的向終點方向跳躍。一次跳躍的距離是S到T之間的任意正整數（包括S,T）。當青蛙跳到或跳過坐標為L的點時，就算青蛙已經跳出了獨木橋。?

　　題目給出獨木橋的長度L，青蛙跳躍的距離范圍S,T，橋上石子的位置。你的任務是確定青蛙要想過河，最少需要踩到的石子數。?

　　對于30%的數據，L?<=?10000；?
　　對于全部的數據，L?<=?10^9。

輸入格式

輸入的第一行有一個正整數L（1?<=?L?<=?10^9），表示獨木橋的長度。第二行有三個正整數S，T，M，分別表示青蛙一次跳躍 的最小距離，最大距離，及橋上石子的個數，其中1?<=?S?<=?T?<=?10，1?<=?M?<=?100。第三行 有M個不同的正整數分別表示這M個石子在數軸上的位置（數據保證橋的起點和終點處沒有石子）。所有相鄰的整數之間用一個空格隔開。?

輸出格式

輸出只包括一個整數，表示青蛙過河最少需要踩到的石子數。?

測試樣例1

輸入

10
2 3 5
2 3 5 6 7

輸出

2

思路:因為只有100個點，數字很大，需要壓縮路徑，兩點之間的距離不能變，取了（1-10）的最小公倍數；

　　　簡單dp一下；代碼搓。。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define esp 0.00000000001
const int N=1e3+10,M=1e6+10,inf=1e9+10,mod=1000000007;
int a[N];
int step[N];
int dp[M];
int flag[M];
int gcd(int x,int y)
{return y==0?x:gcd(y,x%y);
}
int main()
{int lcm=1;for(int i=2;i<=10;i++)lcm=lcm*i/gcd(lcm,i);int x,y,z,i,t;int L,st,en,m;while(~scanf("%d",&L)){memset(flag,0,sizeof(flag));for(i=0;i<=M;i++)dp[i]=inf;scanf("%d%d%d",&st,&en,&m);dp[0]=0;for(i=1;i<=m;i++)scanf("%d",&a[i]);a[m+1]=L;sort(a+1,a+2+m);for(i=1;i<=m+1;i++){if(a[i]-a[i-1]>=2520)step[i]=step[i-1]+2520+(a[i]-a[i-1])%2520;elsestep[i]=step[i-1]+a[i]-a[i-1];flag[step[i]]=1;}flag[step[m+1]]=0;for(i=0;i<=step[m+1];i++){for(t=i+st;t<=i+en;t++)if(flag[t])dp[t]=min(dp[i]+1,dp[t]);elsedp[t]=min(dp[i],dp[t]);}int ans=inf;for(i=step[m+1];i<=step[m+1]+en;i++)ans=min(ans,dp[i]);printf("%d\n",ans);}return 0;
}

?