太原网站关键词优化,wordpress academy主题,盐亭县建设局网站,网站怎么优化自己免费描述 在河上有一座独木桥#xff0c;一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子#xff0c;青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数#xff0c;我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点#xff1a;0一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点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 样例输入1 10
2 3 5
2 3 5 6 7 样例输出1 2 限制 1s 由于路径太长所以可以剪去一些不必要的路径。 可以发现当路径长度剪去n个s*t时对后面是没有影响的但是当s1t2L6时会发现是不能剪完的必须要留出一个s*t。 还有st的特判此时走过的路径是固定的单独处理即可。 DP转移方程 ans[i]min(ans[i-j]k[i],ans[i]);(i为posj为步长) 1 #includecstdio2 #includeiostream3 #includecmath4 #includecstring5 #includealgorithm6 #includecstdlib7 using namespace std;8 long long l,s,t,m;9 long long map[1000005];
10 long long k[1000005];
11 long long pos[105];
12 long long ans[1000005];
13 long long min(long long x,long long y)
14 {
15 if(xy)return x;
16 return y;
17 }
18 int main()
19 {
20 for(int i0;i1000004;i)
21 ans[i]99999999;
22 scanf(%I64d%I64d%I64d%I64d,l,s,t,m);
23 long long mods*t;
24 for(int i1;im;i)
25 scanf(%I64d,pos[i]);
26 sort(pos1,posm1);
27 int temp0;
28 for(int i1;im;i)
29 {
30 long long chapos[i]-pos[i-1];
31 long long qwecha;
32 cha%mod; qwe/mod;
33 tempcha;
34 if(qwe!0)
35 tempmod;
36 k[temp]1;
37 }
38 temps*t;
39 if(st)
40 {
41 long long u0;long long vs;int an0;
42 while(utemp)
43 {
44 uv;
45 if(k[u])an;
46 }
47 printf(%d,an);
48 exit(0);
49 }
50 for(int i0;is-1;i)
51 ans[i]0;
52 for(int is;itemp;i)
53 {
54 for(int js;jt;j)
55 {
56 if(i-j0)break;
57 if(i-j0i-js)continue;
58 ans[i]min(ans[i-j]k[i],ans[i]);
59 }
60 }
61 printf(%I64d,ans[temp]);
62 } 转载于:https://www.cnblogs.com/937337156Zhang/p/6044183.html
