ZHK

ZHK

一只叫ZHK的蒟蒻为了RP而战

题解 P1052 【过河】

posted on 2019-11-23 16:59:25 | under 题解 |

博客园体验更佳

显然是 $dp$ ,是用 $STL$ 当中的 $map$ 可以做到30分

#include <bits/stdc++.h>//万能头文件
using namespace std;
int l,n,s,t;
map<int,bool>m;//记有没有石头
map<int,int>dp;//最少踩到石头的个数
int main(){
    cin>>l>>s>>t>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        m[x]=true;
    }
    for(int i=1;i<=l+t-1;i++){
        dp[i]=INT_MAX/2;
        for(int j=s;j<=t&&j<=i;j++)dp[i]=min(dp[i],dp[i-j]);//倒退
        if(m[i])dp[i]++;
    }int s=dp[l];
    for(int i=l+1;i<=l+t-1;i++)s=min(s,dp[i]);
    cout<<s;
    return 0;
}

之后,我们该想一想如何 $AC$ 这道题

我们发现石头数量很少,而独木桥却很长

360截图18141224304435.png

遇到这张图,我们可能还会选择暴力的方法

360截图170405117195111.png

但是遇到这张图,你还会用暴力吗?

空的地方就是随便走就行了,完全可以不用老老实实的去看,我们可以把路径压缩,更简单地说就是如果后面的一个石头与前面的一个石头距离太远,我们可以把后面一个石头推到前一个石头附近,至于这个量是多少呢,需要自己把握。

我自己还是觉得稍微保险一点,不要 $TLE$ 就行了,所以我选择把这个数定在 $1000$ ,当然听同学说,他定的比较小也过了,这并没有关系。

所以,我们可以看代码了

#include<bits/stdc++.h>
using namespace std;
int l,s,t,m,a[110],dp[100010],b[110];
bool x[100010];
int main(){
    cin>>l;
    cin>>s>>t>>m;
    for(int i=1;i<=m;i++)cin>>a[i];
    sort(a+1,a+1+m);
    if(s==t){//这个应该很简单,我上面没有说
        int ans=0;
        for(int i=1;i<=m;i++)
            if(a[i]%s==0)ans++;//如果会经过它,答案+1
        cout<<ans;//输出
        return 0;
    }
    for(int i=1;i<=m;i++)
        if(a[i]-a[i-1]>1000)b[i]=b[i-1]+1000;//注意啦,如果原来的距离小于1000,你要保持不变
        else b[i]=a[i]-a[i-1]+b[i-1];
    for(int i=1;i<=m;i++)x[b[i]]=true;//石头
    l=b[m];
    for(int i=1;i<=l+t-1;i++){
        dp[i]=INT_MAX/2;
        for(int j=s;j<=t&&j<=i;j++)dp[i]=min(dp[i],dp[i-j]);//转移状态
        if(x[i])dp[i]++;
    }int ans=dp[l];
    for(int i=l;i<=l+t-1;i++)ans=min(ans,dp[i]);//打擂法求最小值
    cout<<ans;//输出
    return 0;
}