过河 | FFY's Blog

题意

P1052 过河

• 排序
• 离散化
• DP

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

1#include<cstdio>
2#include<algorithm>
3#include<cstring>
4using namespace std;
5const int maxn=2e3+10;
6int l,s,t,m,n;
7int f[maxn],lo[200];
8bool use[maxn];
9int main()
10{
11    scanf("%d%d%d%d",&amp;l,&amp;s,&amp;t,&amp;m);
12    memset(f,0x3f,sizeof f);f[0]=0;
13    for(int i=1;i<=m;i++)scanf("%d",&amp;lo[i]);
14    sort(lo+1,lo+1+m);
15    for(int i=1;i<=m;i++)
16    {
17        if(lo[i]-lo[i-1]>=t)n+=(lo[i]-lo[i-1])%t+t;
18        else n+=(lo[i]-lo[i-1]);
19        use[n]=true;
20    }
21    n+=(l-lo[m])%t;
22    for(int i=1;i<=n+t-1;i++)
23    {
24        for(int j=s;j<=t;j++)if(i-j>=0)
25        f[i]=min(f[i],f[i-j]);
26        if(use[i])f[i]++;
27    }
28    int ans=1e9;
29    for(int i=n;i<=n+t-1;i++)ans=min(ans,f[i]);
30    printf("%d\n",ans);
31    return 0;
32}