怎样做网站的二维码,2019河北省建设厅检测员报名网站,旅游网站建设策划方案书,公司注册资金需要实际缴纳吗题目描述 在河上有一座独木桥#xff0c;一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子#xff0c;青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数#xff0c;我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点#xff1a;0… 题目描述 在河上有一座独木桥一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点0,1,…,L0,1,…,L0,1,…,L其中LLL是桥的长度。坐标为000的点表示桥的起点坐标为LLL的点表示桥的终点。青蛙从桥的起点开始不停的向终点方向跳跃。一次跳跃的距离是SSS到TTT之间的任意正整数包括S,TS,TS,T。当青蛙跳到或跳过坐标为LLL的点时就算青蛙已经跳出了独木桥。 题目给出独木桥的长度LLL青蛙跳跃的距离范围S,TS,TS,T桥上石子的位置。你的任务是确定青蛙要想过河最少需要踩到的石子数。 输入输出格式 输入格式 第一行有111个正整数L(1≤L≤109)L(1 \le L \le 10^9)L(1≤L≤109)表示独木桥的长度。 第二行有333个正整数S,T,MS,T,MS,T,M分别表示青蛙一次跳跃的最小距离最大距离及桥上石子的个数其中1≤S≤T≤101 \le S \le T \le 101≤S≤T≤10,1≤M≤1001 \le M \le 1001≤M≤100。 第三行有MMM个不同的正整数分别表示这MMM个石子在数轴上的位置数据保证桥的起点和终点处没有石子。所有相邻的整数之间用一个空格隔开。 输出格式 一个整数表示青蛙过河最少需要踩到的石子数。 输入输出样例 输入样例#1 10
2 3 5
2 3 5 6 7输出样例#1 2说明 对于30%的数据L≤10000L \le 10000L≤10000 对于全部的数据L≤109L \le 10^9L≤109。 2005提高组第二题 思路 如果不考虑数据范围的话可以很快得出递推关系式dp[i]min(dp[ik]a[i]) (S≤k≤T)dp[i]min(dp[ik]a[i])\ \ (S\leq k \leq T)dp[i]min(dp[ik]a[i]) (S≤k≤T)a[i]a[i]a[i]为iii点的石头数dp[i]dp[i]dp[i]表示到达iii点踩到的最少石头数 然鹅看了数据范围后时间和空间都是过不去的。所以需要选择别的方法 当STSTST的时候可以很容易得到所有在SSS倍数位置上的点都会走到所以对该种情况进行特判 我们可以发现石子在桥上放置的是非常稀疏的而且当点的位置超过一定范围点都是可以跳到的。所以可以将石子所在的位置压缩到这个范围里去。将压缩后位置储存起来作为新的石头的位置按照这个位置进行dp即可 假设每次走ppp或者p1p1p1步.我们知道gcd(p,p1)1gcd(p,p1)1gcd(p,p1)1. 由扩展欧几里得可知对于二元一次方程组px(p1)ygcd(p,p1)px(p1)ygcd(p,p1)px(p1)ygcd(p,p1)是有整数解的即可得px(p1)yspx(p1)yspx(p1)ys是一定有整数解的。 设px(p1)yspx(p1)yspx(p1)ys的解为xx0(p1)t,yy0−ptxx_0(p1)t,yy_0−ptxx0(p1)t,yy0−pt。令0≤x≤p0\leq x\leq p0≤x≤p(通过增减ttt个p1p1p1来实现)sgt;p×(p1)−1sgt;p\times (p1)−1sp×(p1)−1 则有ys−pxp1≥s−p2p1gt;p(p1)−1−pxp1≥0y\dfrac {s-px}{p1}\geq \dfrac {s-p^{2}}{p1} gt;\dfrac {p\left( p1\right) -1-px}{p1}\geq 0yp1s−px≥p1s−p2p1p(p1)−1−px≥0 即表示当s≤p×(p1)s\leq p\times (p1)s≤p×(p1)时px(p1)yspx(p1)yspx(p1)ys有两个非负整数解每次走ppp步或者p1p1p1步p×(p1)p\times (p1)p×(p1)之后的地方均能够到达。 如果两个石子之间的距离大于p×(p1)p\times (p1)p×(p1)那么就可以直接将他们之间的距离更改为p×(p1)p \times (p1)p×(p1)。 综上得到压缩路径的方法若两个石子之间的距离大于t×(t−1)t\times(t−1)t×(t−1)则将他们的距离更改为t×(t−1)t\times (t−1)t×(t−1)。 因为t≤10为t\leq10为t≤10因此我们可以直接将大于10×910\times910×9的距离直接化为909090. 关于路径压缩常数的选择证明过程详见https://blog.csdn.net/qq_34940287/article/details/77494073 AC代码 /************************************************************************* Author: WZY School: HPU Created Time: 2019-02-03 15:55:49************************************************************************/
#include bits/stdc.h
#define ll long long
#define ull unsigned long long
#define ms(a,b) memset(a,b,sizeof(a))
#define INF 0x7f7f7f7f
const int maxn1e610;
const int mod1e97;
using namespace std;
int a[maxn];
int dp[maxn];
int vis[maxn];
int main(int argc, char const *argv[])
{ios::sync_with_stdio(false);cin.tie(0);int L;int ans0;int s,t,m;cinL;cinstm;for(int i1;im;i)cina[i];if(st){for(int i1;im;i){if(a[i]%s0)ans;}coutansendl;return 0;}sort(a1,a1m);int _90;int resa[1]%_;vis[res]1;// 缩点for(int i2;im;i){res(a[i]-a[i-1])%_;vis[res]1;}for(int ires;i0;i--){dp[i]INF;for(int js;jt;j)dp[i]min(dp[i],dp[ij]vis[i]);}coutdp[0]endl;return 0;
} 转载于:https://www.cnblogs.com/Friends-A/p/11054978.html
