模板自助建站网站制作,php企业网站demo,阿里巴巴网站被关闭了要怎么做,大连手机自适应网站建设P1059 过河时间: 1000ms / 空间: 131072KiB / Java类名: Main背景 NOIP2005 提高组 第二道描述 在河上有一座独木桥#xff0c;一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子#xff0c;青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都 是正整…P1059 过河 时间: 1000ms / 空间: 131072KiB / Java类名: Main 背景 NOIP2005 提高组 第二道 描述 在河上有一座独木桥一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都 是正整数我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点01……L其中L是桥的长度。坐标为0的点表示桥的起点坐标为L的点表 示桥的终点。青蛙从桥的起点开始不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数包括S,T。当青蛙跳到或跳过坐标为L的点时就算青蛙已经跳出了独木桥。 题目给出独木桥的长度L青蛙跳跃的距离范围S,T桥上石子的位置。你的任务是确定青蛙要想过河最少需要踩到的石子数。 对于30%的数据L 10000 对于全部的数据L 10^9。 输入格式 输入的第一行有一个正整数L1 L 10^9表示独木桥的长度。第二行有三个正整数STM分别表示青蛙一次跳跃 的最小距离最大距离及桥上石子的个数其中1 S T 101 M 100。第三行 有M个不同的正整数分别表示这M个石子在数轴上的位置数据保证桥的起点和终点处没有石子。所有相邻的整数之间用一个空格隔开。 输出格式 输出只包括一个整数表示青蛙过河最少需要踩到的石子数。 测试样例1 输入 10 2 3 5 2 3 5 6 7 输出 2 思路:因为只有100个点数字很大需要压缩路径两点之间的距离不能变取了1-10的最小公倍数 简单dp一下代码搓。。 #includebits/stdc.h
using namespace std;
#define ll long long
#define esp 0.00000000001
const int N1e310,M1e610,inf1e910,mod1000000007;
int a[N];
int step[N];
int dp[M];
int flag[M];
int gcd(int x,int y)
{return y0?x:gcd(y,x%y);
}
int main()
{int lcm1;for(int i2;i10;i)lcmlcm*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(i0;iM;i)dp[i]inf;scanf(%d%d%d,st,en,m);dp[0]0;for(i1;im;i)scanf(%d,a[i]);a[m1]L;sort(a1,a2m);for(i1;im1;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[m1]]0;for(i0;istep[m1];i){for(tist;tien;t)if(flag[t])dp[t]min(dp[i]1,dp[t]);elsedp[t]min(dp[i],dp[t]);}int ansinf;for(istep[m1];istep[m1]en;i)ansmin(ans,dp[i]);printf(%d\n,ans);}return 0;
} 转载于:https://www.cnblogs.com/jhz033/p/5713756.html
