过河 | FFY's Blog

题意

P1052 过河

• 排序
• 离散化
• DP

桥很长,不能直接DP;而石子数比较少,这时我们想到离散化;
当两点间的距离$d$大于$t$时,一定可以由d%t跳过来,所以最多只需要t+d%t种距离的状态就可以表示这两个石子之间的任意距离关系.这样就把题目中的$10^9$压缩成了$2\times t\times m$最多不超过$2000$,然后就可以放心大胆地用DP了.不过要注意题目中的”当青蛙跳到或跳过坐标为L的点时.就算青蛙已经跳出了独木桥”,所以DP的终点是一个范围而非确切的一个点，最后还要在这个范围内取最小值。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=2e3+10;
int l,s,t,m,n;
int f[maxn],lo[200];
bool use[maxn];
int main()
{
    scanf("%d%d%d%d",&l,&s,&t,&m);
    memset(f,0x3f,sizeof f);f[0]=0;
    for(int i=1;i<=m;i++)scanf("%d",&lo[i]);
    sort(lo+1,lo+1+m);
    for(int i=1;i<=m;i++)
    {
        if(lo[i]-lo[i-1]>=t)n+=(lo[i]-lo[i-1])%t+t;
        else n+=(lo[i]-lo[i-1]);
        use[n]=true;
    }
    n+=(l-lo[m])%t;
    for(int i=1;i<=n+t-1;i++)
    {
        for(int j=s;j<=t;j++)if(i-j>=0)
        f[i]=min(f[i],f[i-j]);
        if(use[i])f[i]++;
    }
    int ans=1e9;
    for(int i=n;i<=n+t-1;i++)ans=min(ans,f[i]);
    printf("%d\n",ans);
    return 0;
}