标签：NOIP2005 le int luogu 青蛙 P1052 lcm dp define

[NOIP2005 提高组] 过河

题目描述

在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：\(0,1,\cdots,L\)（其中 \(L\) 是桥的长度）。坐标为 \(0\) 的点表示桥的起点，坐标为 \(L\) 的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是 \(S\) 到 \(T\) 之间的任意正整数（包括 \(S,T\)）。当青蛙跳到或跳过坐标为 \(L\) 的点时，就算青蛙已经跳出了独木桥。

题目给出独木桥的长度 \(L\)，青蛙跳跃的距离范围 \(S,T\)，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。

输入格式

输入共三行，

第一行有 \(1\) 个正整数 \(L\)，表示独木桥的长度。
第二行有 \(3\) 个正整数 \(S,T,M\)，分别表示青蛙一次跳跃的最小距离，最大距离及桥上石子的个数。
第三行有 \(M\) 个不同的正整数分别表示这 \(M\) 个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。

输出格式

一个整数，表示青蛙过河最少需要踩到的石子数。

样例 #1

样例输入 #1

10
2 3 5
2 3 5 6 7

样例输出 #1

提示

【数据范围】

对于 \(30\%\) 的数据，\(1\le L \le 10^4\)；
对于 \(100\%\) 的数据，\(1\le L \le 10^9\)，\(1\le S\le T\le10\)，\(1\le M\le100\)。

【题目来源】

NOIP 2005 提高组第二题

思路

首先我们先来第一种比较好想的做法
我们a,b两点路径的距离可以%lcm(s,s+1,...t-1,t)
但是还是有特殊情况就是我们当前本来是大于这个lcm的但是模了之后小于t了
我们本来要在期间跳很多次结果直接可以一次跳过去显然是不合法的我们要+上一个lcm

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
const int M = 998244353;
const int mod = 998244353;
#define int long long
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int dp[N+1];
int gcd(int b,int c){return c==0?b:gcd(c,b%c);}
int lcm(int b,int c){return b * c/ gcd(b, c);}
void solve() {
    int n,s,t,m;cin>>n>>s>>t>>m;
    set<int>st;
    int q=1;
    for(int i=s;i<=t;i++)q=lcm(i,q);
    vector<int>a(m+1),c(m+2);
    for(int i=1;i<=m;i++)cin>>a[i];
    a.push_back(n);
    sort(all(a));
    for(int i=1;i<=m+1;i++)c[i]=a[i]-a[i-1];
    if(s==t){
        int cnt=0;
        for(int i=1;i<=m;i++){
            if(a[i]%s==0)cnt++;
        }
        cout<<cnt<<endl;return;
    }
    for(int i=1;i<=m+1;i++) {
        a[i]=a[i-1]+(c[i]%q);
        if(a[i]-a[i-1]<=t&&c[i]>=q)a[i]+=q;
        if(i!=m+1)st.insert(a[i]);
    }
    n=a[m+1];
    memset(dp,0x3f3f,sizeof dp);
    dp[0]=0;
    for(int i=1;i<=n+10;i++)
        for(int j=s;j<=t;j++)
            if(i-j>=0)dp[i]=min(dp[i],dp[i-j]+(st.count(i)==1));
    int ans=INF;
    for(int i=n;i<=n+10;i++)ans=min(ans,dp[i]);
    cout<<ans<<endl;
}
signed main(){
    fast
    int T;T=1;
    while(T--) {
        solve();
    }
    return ~~(0^_^0);
}

另一种很厉害的做法就是
我们知道lcm（s，t）之后肯定是被覆盖完全的注意这里的lcm不同了
所以要是距离大于了lcm（s，t）我们直接让其等于lcm即可
为什么我们设a，b左右端点
a端点能到达st 但是这样都是dp为1
而我们只要是a左边或者右边的都会将dp min为0
我们只有st这个区间时我们才有机会将一些变成1
其余再多一厘米也是徒劳
最后都不要忘记判断s=t的情况
因为lcm=1 我们无法用常规情况求解了

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
const int M = 998244353;
const int mod = 998244353;
#define int long long
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int dp[N+1];
int gcd(int b,int c){return c==0?b:gcd(c,b%c);}
int lcm(int b,int c){return b * c/ gcd(b, c);}
void solve() {
    int n,s,t,m;cin>>n>>s>>t>>m;
    set<int>st;
    vector<int>a(m+1),c(m+2);
    for(int i=1;i<=m;i++)cin>>a[i];
    a.push_back(n);
    sort(all(a));
    for(int i=1;i<=m+1;i++)c[i]=a[i]-a[i-1];
    if(s==t){
        int cnt=0;
        for(int i=1;i<=m;i++){
            if(a[i]%s==0)cnt++;
        }
        cout<<cnt<<endl;return;
    }
    for(int i=1;i<=m+1;i++){
        if(c[i]>=lcm(s,t))a[i]=a[i-1]+lcm(s,t);
        else a[i]=a[i-1]+c[i];
        if(i!=m+1)st.insert(a[i]);
    }
    n=a[m+1];
    memset(dp,0x3f3f,sizeof dp);
    dp[0]=0;
    for(int i=1;i<=n+10;i++)
        for(int j=s;j<=t;j++)
            if(i-j>=0)dp[i]=min(dp[i],dp[i-j]+(st.count(i)==1));
    int ans=INF;
    for(int i=n;i<=n+10;i++)ans=min(ans,dp[i]);
    cout<<ans<<endl;
}
signed main(){
    fast
    int T;T=1;
    while(T--) {
        solve();
    }
    return ~~(0^_^0);
}

标签：NOIP2005,le,int,luogu,青蛙,P1052,lcm,dp,define
From： https://www.cnblogs.com/ycllz/p/16733154.html

luogu P1052 [NOIP2005 提高组] 过河